比较难的一道二分题，我们可以设x为一共扔出的次数，也就是说进行了x次扔出k个球的操作，那么扔出的球就是k*x个
接下来，假设每一种球有n中，那我们最多扔出的该颜色球就是min(x,n)个，只用检查扔出所有球的个数和kx的大小关系即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<bits/stdc++.h>
using i64=long long;
#define rep(i,a,n) for(i64 i=(a);i<=(n);i++)
#define per(i,a,n) for(i64 i=(n);i>=(a);i--)
#define mst(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N = 2e5 + 9;
i64 a[N], n, k, nw;
bool check(i64 x)
{
nw = 0;
rep(i, 1, n) nw += min(x, a[i]);
if(nw / k >= x) {return true;}
return false;
}
int main()
{
cin>>n>>k;
rep(i, 1, n) cin>>a[i];
i64 l = 0ll, r = 1e15, ans = 0ll;
while(l <= r)
{
i64 mid = (l + r) >> 1;
if(check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans << '\n';
return 0;
}
|
后续可能继续更新
