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;
}