题意： 给定 n n n种花，第 i i i种有 a i a_i ai朵，一束花由 m m m朵互不相同种类的花组成，问最多可以组成多少束花。 数据范围： 1 ≤ n , m ≤ 3 × 1 0 5 , 1 ≤ a i ≤ 1 0 9 1\leq n,m\leq 3\times10^5,1\leq a_i\leq 10^9 1≤n,m≤3×105,1≤ai≤109
题解： 二分答案，设当前答案为 x x x，判断答案是否合法，合法则真实答案至少为 x x x，否则真实答案至多为 x − 1 x-1 x−1。判断条件是每种花取 c i = m i n ( x , a i ) c_i=min(x,a_i) ci=min(x,ai)，最后判断 s u m ≥ ∑ c i sum \geq \sum c_i sum≥∑ci是否成立即可。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<stack> #include<queue> #include<map> #include<vector> #include<cmath> using namespace std; typedef long long ll; template<typename T> inline T Read(){ T s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();} return s * f; } #define read() Read<int>() #define readl() Read<long long>() const int N = 3e5 + 10; ll a[N]; int n, m; bool check(ll x) { ll sum = 0; for(int i = 1; i <= n; i++) sum += min(x, a[i]); return sum >= x * m; } void solve() { n = read(), m = read(); ll sum = 0; for(int i = 1; i <= n; i++) a[i] = readl(), sum += a[i]; ll l = 0, r = sum / m; while(l < r) { ll mid = l + r + 1 >> 1; if(check(mid)) l = mid; else r = mid - 1; } printf("%lld\n", l); } int main() { int T = 1; T = read(); for(int i = 1; i <= T; ++i) { solve(); } return 0; }