https://practice.geeksforgeeks.org/problems/raju-and-coins/0

Raju always like to collect coins. Raju has already managed to collect n different types of coins a1,a2….an . One day he went into the sale and find out that the sale consists of 109 types of coins where i-th type of coin costs i dollars. He decided to buy some more different types of coins given that he does not have that type of coin already. But he has only k dollars to spend.
So help him to choose the type of coins.

Input:

The first line will contain test cases T. Then T Test cases follow. Each of the test cases will contain two integers n, k the number of types of coins that Raju already has and the money he has respectively. The next line contains n distinct integers a1,a2…an the types of coins that Raju already has.

Output:

Print a single integer denoting the number of different types of coins that Raju can buy so that the number of different coins in his collection is maximum. Cost should not exceed k.

Constraints:

1<=T<=27
1<=n<=100000
1<=k<=109
1<=ai<=109

Example:

Input
2
4 14
4 6 12 8
3 7
1 3 4

Output
4
2

用一个数组记录下一个，可选的硬币的位置

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 #include <bits/stdc++.h>
using namespace std;
#define sf(n) scanf("%d",&(n))
#define pf(n) printf("%d",n)
#define pfn(n) printf("%d\n",n)
#define fi(s,t) for(i=s;i<t;i++)
#define fj(s,t) for(j=s;j<t;j++)
#define mem(a,c) memset(a,c,sizeof(a))
const int MAX=100000+10;
int t,n,k,g,ans,nl[MAX],last,cnt,a[MAX],i,j;
int main(){
	freopen("in","r",stdin);
	ans=0;
	sf(t);
	while(t--){
		mem(nl,0);
		ans=0;cnt=0;
		sf(n);sf(k);
		fi(0,n) {
			sf(a[i]);	
		}
		sort(a,a+n);
		last =0; 
		fi(0,n) {
			if(a[i] > last +1)
				fj(last+1,a[i])
					nl[cnt++] =j;
			last=a[i];
		}
		nl[cnt++] =a[n-1]+1;
		fi(0,cnt){
			if(k >= nl[i]) {
				k-=nl[i];ans ++;
			}else break;
		}
		if(i==cnt) 
			while(k){
				if(k>=i) {
					k-=i;
					ans ++;
					i++;
				}
				else break;
			}
		pfn(ans);
	}
	return 0;
}