原题地址
题意:给从1到n个数,然后q次操作,每次操作有两个变量z,x:
当z=1时:要把后面的x从1到n中去掉
当z=2时:查找从x开始,1到n中距离x最近的没被删掉的数
思路一:暴力做,把所有z=1的数用set(或者map等STL)存下来,接着在z=2时for循环从x到n的遍历找到set中没有的数,就输出该数并跳出来,这种做法十分极限且只能在c++11且输入输出为scanf和printf的情况下,才能通过,属于侥幸过题(虽然比赛的时候没做出。。)
思路二:当使用map写超时了,后来才想到用unordered_map这个数据结构。其实就是用这个模拟并查集。
(大佬思路)
思路一代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
	set<int> a;
	int n , q;
	scanf("%d %d",&n,&q);
	for(int i=1;i<=q;i++){
		int z, x;
		scanf("%d %d",&z,&x);
		if(z==1)
			a.insert(x);
		else if(z==2){
			for(int i=x;i<=n;i++){
				if(a.count(i)==0){
					printf("%d\n",i);break;
				}
						
			}
			
		}
	}
	return 0;
}

思路二代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
unordered_map<int, int> m;
int find(int x)
{
	if(!m.count(x))
		return x;
	else
		return m[x]=find(m[x]);
} 
int main() {
    int n, q;
    scanf("%d%d",&n,&q);
    int op, x;
    while (q--)
	{
        scanf("%d%d",&op,&x);
        if (op==1){
            m[x]=find(x+1);
        }else{
            int ans=find(x);
            if(ans>n) ans=-1;
            printf("%d\n",ans);
        }
    }
    return 0;
}