【数据结构1-2】P5076 普通二叉树(简化版)(c++,multiset做法)

2023-12-24 06:11:34


一、题目

【深基16.例7】普通二叉树(简化版)

题目描述

您需要写一种数据结构,来维护一些数( 都是 1 0 9 10^9 109 以内的数字)的集合,最开始时集合是空的。其中需要提供以下操作,操作次数 q q q 不超过 1 0 4 10^4 104

  1. 查询 x x x 数的排名(排名定义为比当前数小的数的个数 + 1 +1 +1。若有多个相同的数,应输出最小的排名)。
  2. 查询排名为 x x x 的数。
  3. x x x 的前驱(前驱定义为小于 x x x,且最大的数)。若未找到则输出 ? 2147483647 -2147483647 ?2147483647
  4. x x x 的后继(后继定义为大于 x x x,且最小的数)。若未找到则输出 2147483647 2147483647 2147483647
  5. 插入一个数 x x x

输入格式

第一行是一个整数 q q q,表示操作次数。

接下来 q q q 行,每行两个整数 o p , x op,x op,x,分别表示操作序号以及操作的参数 x x x

输出格式

输出有若干行。对于操作 1 , 2 , 3 , 4 1,2,3,4 1,2,3,4,输出一个整数,表示该操作的结果。

样例 #1

样例输入 #1

7
5 1
5 3
5 5
1 3
2 2
3 3
4 3

样例输出 #1

2
3
1
5

基本思路:

  • 题目中提到了集合、而且是维护一些数的集合,我想到了STL中的set(底层是平衡树的一种),不过集合元素中右重复的元素,需要用到multiset,可以存放重复的元素并且时升序排序的。
  • 对于操作1,查询x的排名,应为set不支持随机访问,所以需要从头遍历一个一个数,需要注意的是”有多个相同的数,应输出最小的排名“,所以遍历到第一个等于x的数break即可。
  • 操作2,同1,遍历集合。
  • 操作3,再找前驱和后继之前需要初始化一下multiset ,给出一个边界。找x的前驱,用到了STL自带的二分查找lower_bound,返回第一个大于等于x的迭代器。
  • 操作4,使用upper_bound,返回第一个大于x的迭代器,取值后即是x的后继。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 1000010;
multiset<int> s; 
const int INF = 2147483647;

void solve(){
	int op,x;
	cin>>op>>x;
	if(op==1){//查询x数的排名
		int num=0;
		for(auto i:s)
		  if(i<x) num++;//注意是<
		  else break;
		cout<<num<<endl;
	}else if(op==2){//查询排名为x的数
		int num=-1;
		for(auto i:s){
			num++;
			if(num==x){
				cout<<i<<endl;
				break;
			}
		}
	}else if(op==3){//x的前驱
		cout<<*(--s.lb(x))<<endl;
	}else if(op==4){//x的后继
		cout<<*(s.ub(x))<<endl;
	}else{//将x插入集合
		s.insert(x);
	}
	
}

signed main(){
	IOS;
	int T=1;
	cin>>T;
	s.insert(INF),s.insert(-INF);
	while(T--){
		solve();
	}
	return 0;
}

文章来源:https://blog.csdn.net/2301_77012063/article/details/135171269
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。