C. Cards Partition 【Codeforces Round 975 (Div. 2)】

C. Cards Partition

思路：

可以O(n)直接判断，牌组从大到小依次遍历即可。
不要用二分答案，因为答案不一定是单调的

代码:

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
int a[200005];
int n, k, sum = 0, ans = 0,maxn=0;

bool check(int x){
if(x==1)return true;
int mzs=0;
if(n>1){mzs = (sum-maxn)/(x-1);}
int zs=sum/x;
if(zs > mzs) zs = mzs;
int ys=sum - zs*x;
int dy=max(0LL,maxn-zs);
if(ys>0)dy=max(1LL,dy);
return (dy*x)<=k+ys;
}


void solve() {
sum = 0;
ans = 1;
maxn = 0;
memset(a, 0, sizeof(a));
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
maxn = max(maxn,a[i]);
sum += a[i];
}

for (int i = n; i >= 1; i--) {
if (check(i)) {
ans = i;
break;
}
}

cout << ans << endl;
}

signed main() {
cin.tie(0)->ios::sync_with_stdio(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/2303_79310336/article/details/142612702

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！