1 条题解
-
0
赛时这题我都没做出来，我退役吧 \kk。
思路还是比较简单的。
就是考虑每次选 个数，就相当于有 个盒子，你需要把数放进去。
但你不能在一个时刻把一个数放到两个盒子中。
此时一个思路就是二分答案，因为答案显然满足单调性。
设当前的答案是 。
那么一个东西可以放最多 次。
贪心一下，把这个东西加起来，和 比较一下就好了。
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; int n,k; ll a[N]; int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); ll l=0,r=1e18/k;//防止炸long long while(l+1<r){ ll mid=l+r>>1ll,sum=0; for(int i=1;i<=n;i++)sum+=min(mid,a[i]); if(sum>=1ll*mid*k)l=mid; else r=mid; } ll sum=0; for(int i=1;i<=n;i++)sum+=min(r,a[i]); if(sum>=1ll*r*k)printf("%lld",r); else printf("%lld",l); }
- 1
信息
- ID
- 52
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者
-
houzhiyuan