比较麻烦的二分
需要注意的是并不是选出一个可以最lucky的
而是发完他之后
无论后面怎么发都应该是他最lucky
所以可以进行二分搜索
然后判定时判断是因为mid过大还是因为mid过小
#include<stdio.h>
int a[100020];
int n,m,k,sum;
bool judge(int x) {
if((n-k==1&&x>sum)||(n-k==2&&(x>sum-1||x<=sum/2))||x>sum-(n-k-1)||x<=sum-x-(n-k-2))
return false;
for(int i=0; i<=k; i++) {
if(x<=a[i])
return false;
}
return true;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d %d %d",&n,&m,&k);
sum=0;
for(int i=0; i<k; i++) {
scanf("%d",&a[i]);
sum+=a[i];
}
sum=m-sum;
int l=0,r=m,res=0;
while(l<=r) {
int mid=(l+r)/2;
if(judge(mid)) {
res=mid;
r=mid-1;
} else {
if((n-k==1&&mid>sum)||(n-k==2&&mid>sum-1)||mid>sum-(n-k-1))
r=mid-1;
else
l=mid+1;
}
}
if(!res)
printf("Impossible
");
else
printf("%d
",res);
}
return 0;
}