二分查找套牌的数量
bool check(int x){
int sum = 0;
for(int i = 1; i <= n; i ++){
if(c[i] < x) sum += (x - c[i]);
}
if(sum > m || sum > x) return false;
return true;
}
当前枚举的套牌数量x, 如果c[i] < x, 那么我就使用(x - c[i])中Joker来代替c[i]
如果使用的Joker数量大于了m张或者大于了套牌数量, 那就不行!因为首先一共只有m张Joker牌, 然后为什么使用的Joker牌数量不能超过x呢?
如果大于了x, 那么说明一定存在一套牌里面使用了两个或者更多的Joker这与一套牌至多使用一张Joker矛盾了
总代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 100;
int n, m, c[N];
bool check(int x){
int sum = 0;
for(int i = 1; i <= n; i ++){
if(c[i] < x) sum += (x - c[i]);
}
if(sum > m || sum > x) return false;
return true;
}
signed main(){
HelloWorld;
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> c[i];
int l = 1, r = 1e15, ans = 0;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid)){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans << endl;
return 0;
}



京公网安备 11010502036488号