【Codeforces】CF 2019C

Cards Partition

#数论 #枚举 #鸽巢定理

题目描述

You have some cards. An integer between $1$ and $n$ is written on each card: specifically, for each $i$ from $1$ to $n$, you have $a_i$ cards which have the number $i$ written on them.

There is also a shop which contains unlimited cards of each type. You have $k$ coins, so you can buy at most $k$ new cards in total, and the cards you buy can contain any integer between $1$ and $\mathbf{n}$, inclusive.

After buying the new cards, you must partition all your cards into decks, according to the following rules:

• all the decks must have the same size;
• there are no pairs of cards with the same value in the same deck.

Find the maximum possible size of a deck after buying cards and partitioning them optimally.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows. The first line of each test case contains two integers $n$, $k$ ($1\le n\le 2\cdot 10^5$, $0\le k\le 10^{16}$) — the number of distinct types of cards and the number of coins. The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 10^{10}$, $\sum a_i\ge 1$) — the number of cards of type $i$ you have at the beginning, for each $1\le i\le n$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

输出格式

For each test case, output a single integer: the maximum possible size of a deck if you operate optimally.

样例 #1

样例输入 #1

9
3 1
3 2 2
5 4
2 6 1 2 4
2 100
1410065408 10000000000
10 8
7 4 6 6 9 3 10 2 8 7
2 12
2 2
2 70
0 1
1 0
1
3 0
2 1 2
3 1
0 3 3

样例输出 #1

2
3
1
7
2
2
1
1
2

解题思路

首先我们要把$n$个数平均分为大小为$i$组的几组，并且每一组内的数字都要不同，容易想到鸽巢定理，能分多大的组取决出现次数最多的那个数。

因此我们只需要枚举$i$，然后看看能不能用$k$以内的个数来填充，使得出现次数最多的那个数小于组的个数，并且满足 $[i|(sum+k)]$，其中这里的$sum$表示全部的个数和。

代码

const int N = 2e5 + 10;void solve() {int n, k;std::cin >> n >> k;std::vector<int>a(n + 1);int s = 0;for (int i = 1; i <= n; ++i) {std::cin >> a[i];s += a[i];}int maxx = *std::max_element(a.begin() + 1, a.end());int ans = 0;for (int i = 1; i <= n; i++) {if (k < (s + k) % i) continue;if (maxx * i <= s + k - (s + k) % i) {ans = std::max(ans, i);}}std::cout << ans << "\n";}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;while (t--) {solve();}
}