有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;
}
京公网安备 11010502036488号