自动搬运

查看原文

来自洛谷，原作者为

	T_TLucas_Yin 周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上

搬运于2025-08-24 22:55:31，当前版本为作者最后更新于2024-02-25 18:51:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先要明白，要使得有趣的天数更多，就要懂得“节约”。一天要刷 $t$ 个科目，那我们每天就任选 $t$ 个科目，每科只刷一道题。这样可以给每个科目节约更多的题，留用于让后面更多天变得有趣。我们遵循的原则是，任一天只要变得有趣了，我们就停止刷题。也就是说，每天刷 $t$ 个科目，每个科目一道题，坚决不多刷。

又很容易发现，如果 $n$ 天是有趣的，那么肯定有 $(n-1)$ 天是有趣的（这还用证明嘛？有趣的那 $n$ 天里前 $(n-1)$ 天一定是有趣的吧？）。这就启发我们用二分答案的思想。查找最多的有趣天数 $k$。

如何判定一个 $k$ 是否满足条件呢？我们已经知道了让有趣天数尽可能多的刷题策略。在这种策略下，由于每天每科目只刷一道题，所以一个科目 $k$ 天内至多刷 $k$ 道题。不足的自然能有几道刷几道，超过的最多就能刷 $k$ 道。又根据策略，$k$ 天刷且仅刷 $kt$ 道题。我们算一下每个科目 $k$ 天的过题数之和是否超过了下限即可。

别忘了每一天都不有趣的情况。

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000005],sum;
bool check(long long k){
    long long cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=k) cnt+=k;
        else cnt+=a[i];
    }
    return cnt>=k*m;//判断有没有超过（够不够刷）
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){ cin>>a[i];sum+=a[i]; }
    long long l=0,r=sum,mid,k=0;//!下限天数为0!
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1,k=mid;
        else r=mid-1;
    }
    cout<<k;
    return 0;
}