蓝桥杯——可凑成的最大花束数

情人节到了，妮妮学姐的追求者实在太多了，她一共有 n 个追求者，第 i 个追求者赠送了 ai​ 朵颜色相同的花朵。每个追求者赠送的花朵颜色都不同。为了卖掉这些花并将所得款项捐赠给希望小学，妮妮学姐决定将 k 朵颜色不同的花朵打包成一个花束。请问她最多可以打包成多少个花束？

第一行输入两个整数 n 和 k，分别表示妮妮学姐的追求者数量和打包需要的花朵数。

第二行输入 n 个整数 ai​，表示每个追求者赠送的花朵数量。

数据范围保证：1≤n,k≤2×1051≤n,k≤2×105，1≤ai≤1091≤ai​≤109。

输出一个整数表示妮妮学姐最多可以打包成多少个花束。

2 2

5 6

5 说明

我们需要 2 朵不同颜色花朵打包成一个花束。我们有 5 朵某种颜色的花和 6 朵另一种颜色的花。我们可以通过每个花束中取两个不同颜色的花朵来打包 5 个花束。第二个追求者送的花会剩下一朵，但我们无法使用它来打包一个花束。这是我们能做到的最多的，所以答案是 5 。

代码如下：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 2e5 + 9;

ll a[maxn];

ll check(ll x, int n) {

ll res = 0;

for (int i = 1; i <= n; i++){

res += min(a[i], x);

}

return res;

}

int main()

{

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int n, k; cin >> n >> k;

for (int i = 1; i <= n; i++) cin >> a[i];

sort(a + 1, a + n + 1);

ll l = 0, r = 2e32;

while (l + 1 < r) { //二分答案

ll mid = (l + r) / 2;

if (check(mid, n) / mid >= k) l = mid;

else r = mid;

}

cout << l;

return 0;

}