GitBook

这里写图片描述

比较麻烦的二分 需要注意的是并不是选出一个可以最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\n");
		else
			printf("%d\n",res);
	}
	return 0;
}

题目地址:【NBUT】[1651]Red packet