题解 SP11814 【EKO - Eko】

发表于 更新于 阅读次数： Waline：
SP11814 【EKO - Eko】题解。

康了一下题解相当不详细啊……

这个题是裸的二分答案

直接用代码讲吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int n,m;//n->N,m->M
long long a[1000005],ans;//注意！每个数≤1000000000，会爆int（所以我们其实可以hack掉@炸毛的龙猫 的题解）
inline bool check(long long d){
    long long cnt=0;
    for (int i=1;i<=n;i++)cnt+=max(a[i]-d,(long long)0);
    return cnt>=m;
}
int main(){
    scanf("%d%d",&n,&m);
    long long l=1,r=0,mid;//敲黑板：三年OI一场空，不开long long见祖宗
    for (int i=1;i<=n;i++)scanf("%lld",&a[i]),r=max(r,a[i]);//很明显下界是1，上界我们定一个最大值
    while(l<=r){//有可能的区间
        mid=(l+r)>>1;
        if (check(mid))ans=max(ans,mid),l=mid+1;//mid是一个可行的答案，那么可能的区间上调，同时更新答案
        else r=mid-1;//否则可能的区间下调
    }
    printf("%lld",ans);
}