Cards Partition

题面翻译

有 $n$ 种纸牌，第 $i$ 种纸牌你初始有 $a_i$ 张。

你可以再多购入 $k$ 张这 $n$ 种纸牌。

买完牌后，你要把这些牌按照下列规则分成若干牌组，满足：
- 牌组大小都相同。
- 任意牌组找不到价值相同的牌对。

要求求出牌组的最大大小。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^4$ )。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ , $k$ ( $1 \leq n \leq 2 \cdot 10^5$ , $0 \leq k \leq 10^{16}$ )–不同类型纸牌的数量和硬币的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $0 \leq a_i \leq 10^{10}$ , $\sum a_i \geq 1$ )–即每个 $1 \leq i \leq n$ 开始时拥有的 $i$ 类型的纸牌数量。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

translate by Hoks

题目描述

DJ Genki vs Gram - Einherjar Joker

⠀

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 $ \mathbf{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 \leq n \leq 2 \cdot 10^5 $ , $ 0 \leq k \leq 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, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^{10} $ , $ \sum a_i \geq 1 $ ) — the number of cards of type $ i $ you have at the beginning, for each $ 1 \leq i \leq 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

提示

In the first test case, you can buy one card with the number $ 1 $ , and your cards become $ [1, 1, 1, 1, 2, 2, 3, 3] $ . You can partition them into the decks $ [1, 2], [1, 2], [1, 3], [1, 3] $ : they all have size $ 2 $ , and they all contain distinct values. You can show that you cannot get a partition with decks of size greater than $ 2 $ , so the answer is $ 2 $ .

In the second test case, you can buy two cards with the number $ 1 $ and one card with the number $ 3 $ , and your cards become $ [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5] $ , which can be partitioned into $ [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5] $ . You can show that you cannot get a partition with decks of size greater than $ 3 $ , so the answer is $ 3 $ .

把数组从大到小排序，求最大值，牌堆数必须要比最大值大，把横坐标当作牌堆大小，纵坐标当作牌堆数，应该把堆满一个纵坐标再堆下一个纵坐标，可以保证不会出现有相同的在同一牌堆，而不是堆满一个牌堆再堆下一个牌堆，这样非常麻烦，从大到小枚举牌堆大小

const int N = 2e5 + 10;
int a[N];

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

    for (int i = n; i >= 1; i--)
    {
        int p = (ans + k) / i;

        if (k >= (i - ans % i) % i && p >= mmax) {
            cout << i << "\n";
            return;
        }
    }
}