P10184 whk 题解

T_TLucas_Yin · 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;
}