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

题目链接：题目

大意：

给出若干种卡片，每种卡片有一定数量，你可以加入不超过$k$张任意已给出种类的卡片，使得它们可以被分成若干组，每组容量一定，且同组内不存在相同种类的卡片，求出最大能成立的容量。

思路：

这题的两个关键点在于，一找到可以分配成功的条件，二正确处理各种变量的关系。
这个条件乍一看有点复杂，单看每一组不知道要装什么数字，那么先关注一些必要条件，首先所有卡片的总和要整除每组的容量，并且每种卡片的卡牌数量都不能超过组数，否则由于抽屉原理，肯定会存在有卡片没地方装，被迫和自己兄弟挤在一起。这时候你发现这些就是充分条件，想象你把每种卡片尽可能地放在不同组中，一层层地放满后，一定能够成立，不会有冲突。
接着我们得到条件就是$sum\%l=0$且单种卡片最大数量$max<=sum/l$，如何把$k$加入其中呢？请看代码。
（一开始不敢写是因为以为卡片数量总和超过long long，后来发现最多可能也就到1e16，long long是9e18）

代码：

#include <bits/stdc++.h>
using namespace std;#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define vec vectorvoid solve(){int n, k;cin >> n >> k;vec<int> a(n + 1);for(int i = 1; i <= n; i++){cin >> a[i];}int mx = *max_element(a.begin(), a.end());int sum = accumulate(a.begin(), a.end(), 0ll);int ans = 0;for(int l = n; l >= 1; l--){if(sum % l == 0 && mx * l <= sum + (k / l) * l){ans = l;break;}if(l - (sum % l) <= k && mx * l <= (sum + l - (sum % l)) + ((k - (l - (sum % l))) / l) * l){ans = l;break;}}cout << ans << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin >> t;while(t--){solve();}return 0;
}