游戏公司开发了一套新的手游,在市场上做一个调查,依次去找n名顾客(按顺序),已知第i位顾客会评论的条件是已经至少有ai个评论或他对这个手游感兴趣,但是这n名顾客开始都不感兴趣。计算至少要说服几名顾客对这套手游感兴趣才能至少收到m个人的评论。
输入格式 输入文件名:erfen.in第一行为正整数t(≤5),表示数据组数;每组数据中,第一行为正整数n和m(m≤n≤2*105),第二行为n个正整数ai(≤105)。
输出格式 输出文件名:erfen.out对于每组数据,输出至少要说服的顾客数量。
输入/输出例子1输入:
2
7 4
2 1 3 3 4 2 3
7 4
2 1 3 3 4 3 2
输出:
1
2
样例解释样例1中,先说服1号顾客,则可以收到1,2,6,7四名顾客的评论;样例2中,则需要说服1,3号顾客,可以收到1,2,3,7四名顾客的评论。
#includeusing namespace std; int n,m; int a[1000000]; int f(int x){ int sum=0; for(int i=1;i<=n;i++){ if(a[i]<=sum){ sum++; } else if(x>0){ x--; sum++; } } return sum; } int main(){ int t; cin>>t; while(t--){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } int l=0,r=n,mid=(l+r)/2; while(l



