有n种牌,和一种万能牌,每一套牌由n种牌各一张组成,在一套牌中万能牌只能代替其中任意一种牌,最多只能用一次。问最多能由多少套牌。
考虑二分。如果二分的答案x,可以凑到x套,那么可能能凑到更多,如果凑不到x,那么只能凑的少一点,满足单调性。
对于二分check来说,对于牌的个数大于等于x的,那么每套都用一张就好了。那么对于少的呢,就需要用万能牌来代替。
判定条件就是看所需要的万能牌num是不是小于等于万能牌的个数m,另外注意,题中说了万能牌在一套牌中,最多只能用一次,
所以所需要的万能牌的个数num还需要满足小于等于x
#include<bits/stdc++.h> using namespace std; #define int long long int n,m; int a[55]; bool check(int x){ int num=0; for(int i=1;i<=n;i++){ if(a[i]<x) num+=x-a[i]; } return num<=m && num<=x ; } signed main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; int l=0,r=2e9,mid; while(l+1<r){ mid=l+r>>1; if(check(mid)) l=mid; else r=mid; } cout<<l; return 0; }