依然是典型的二分。如果可以凑成k张牌,则比k小的也能凑,这时候下界l变成mid+1;如果k张牌凑不成,则比k大的也不能凑,这时候上界变成mid-1.
本题几个需要注意的代码细节:
1.r的初值。极限状态下Ci最大5e8,同时J牌也是5e8,每组要么一张J牌要么一张Ci,能抽出1e9对牌。
2.int的范围略大于2e9,但本题中需要对使用到的J牌数目叠加,就可能超范围了。所以在judge中计算J牌数目时,sum需要开long long.其他变量开int即可。
3.最终答案是使得judge(mid)成立的最大的mid,也是最后一次判断成立的mid.因此,l-1就是最终答案。又因为走出22行的while循环时必有r+1==l,因此答案=l-1=r.
代码如下:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int a[55]; int n,m; bool judge(int mid){ ll sum=0;//记录使用到的J牌数 for(int i=1;i<=n;i++){ if(a[i]<mid){ //数字不够,该位置需要J来凑 sum+=(mid-a[i]); } } if(sum>m || sum>mid) return false;//使用到的J牌数目多于组数,肯定有一组含≥2张J else return true; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; int l=0,r=1e9; while(l<=r){ int mid=(l+r)>>1; if(judge(mid)) l=mid+1; else r=mid-1; } cout << r << "\n"; return 0; }