2021-06-10atcoder解题报告D - Kth Excluded（差分+二分法）

题目传送门：D-Kth Excluded
初看该题，我天真的以为要用到stl的set或list，自我否认之后想到了用缺数二叉搜索拼出该数的方法，苦于没有合适的解法，经学长点拨后才知道原来还有差分数列这种东西，实在是太丢人了呜呜呜呜。
差分在该题的应用就是对应原数列的前面所缺的总数，再通过以前一个被移除数定位所查找的数。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>

using namespace std;
long long s[100009];long long s1[100009];
int main(){
	int n,q;
	cin>>n>>q;	
	for(int i=1;i<=n;++i){
        cin>>s[i];		
	}
	sort(s+1,s+1+n);
	
	for(int i=1;i<=n;++i){
		s1[i]=s[i]-s[i-1]-1+s1[i-1];//构造差分数列
	}
	
	//for(int i=1;i<=n;++i)cout<<i<<":"<<s1[i]<<endl;
		
	for(int i=0;i<q;++i){
		long long b;cin>>b;		
		int h=lower_bound(s1,s1+1+n,b)-s1;//找到能容纳第b号查找的最小差分元素
		cout<<b+s[h-1]-s1[h-1]<<endl;//根据前一被删元素定位所查元素
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

举例：

4 3
3 5 6 7
2
5
3

1
2
3
4
5
6

查找3号元素时，3前有二个未删元素，而5前有三个，定位到5，从3开始再找3-2=1，找到4。
又学到的一点点呢。