P10184 [YDOI R1] whk

alex_liu · 2024-02-25 16:08:52 · 题解

题目传送门

分析

发现如果有 x 天被定义为有趣，则必然有 x-1 天被定义为有趣，答案具有单调性，考虑二分。

如果有 x 天被定义为有趣，那么至少做了 x\times t 道题，每门科目的贡献为 \min(a[i],x)，如果题目有剩余则 x 为有效答案。

时间复杂度 O(n\log m)，m 的最大值为 5\times 10^5\times 10^6=5\times 10^{11}。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int n,t,a[500005];
bool check(int x){
    int now=x*t;
    for(int i=1;i<=n;i++)now-=min(a[i],x);
    return now<=0;
}
signed main(){
    n=read(),t=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int l=1,r=1e12,ans=0;
    while(l+1<r){
        int mid=l+r>>1;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%lld\n",l);
    return 0;
}