通过二分答案的做法,在这里是二分套牌的数量。那么这就转换成了已知套牌的数量如何去验证能不能达到这么多套牌数。
假设有ABC三种套牌:A:3,B:4,C:5。如果已知套牌数量为x那么对ABC来说数量上就得大于等于x,缺少的就需要用joker来补,那么到底需要多少joker就可以算出来。
对于joker,一个最明显的条件就是必须小于m,毕竟只有m张joker。还有就是题目中说一次套牌只能有一张joker,那么joker最多只能用x次。
要注意在计算过程中会超出long long的范围(虽然题目中给的数据没有超出long long范围)。还要注意二分里面最大要开到多少,不能仅仅开到500000000这个会卡一个测试点。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 50+10;
int n, m;
ll c[maxn];
bool yanz(int x) {
ll cnt = 0;
for (int i=0;i<n;i++) {
if (!(x-c[i]<=0))
cnt += x-c[i];
}
if (cnt<=x&&cnt<=m) return true;
return false;
}
int main() {
scanf("%d %d", &n, &m);
for (int i=0;i<n;i++) {
scanf("%lld", c+i);
}
ll l=0, r=1000000001;
while (l<r) {
ll mid = (l+r+1)/2;
if (yanz(mid)) l = mid;
else r = mid-1;
}
cout<<l;
return 0;
}

京公网安备 11010502036488号