社区讨论

二分查找 WA 9个点 求助qwq

P1873[COCI 2011/2012 #5] EKO / 砍树参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lodi9rpb
此快照首次捕获于
2023/10/31 07:02
2 年前
此快照最后确认于
2023/11/06 22:19
2 年前
查看原帖
RT
CPP
#include <bits/stdc++.h>
using namespace std;

#define RE register
#define ll long long

ll n,m,imax=-233333333333;
ll f[1000100];

inline void fread(ll &x){
    x=0;
    ll f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x*=f;
}

inline ll work(ll x){
    //cout<<x<<endl;
    ll ans=0;
    for(RE ll i=1;i<=n;i++){
        if(f[i]>x){
            ans+=f[i]-x;
        }
    }
    return ans;
}

int main(){
    fread(n);
    fread(m);
    for(RE ll i=1;i<=n;i++){
        fread(f[i]);
        imax=max(f[i],imax);
    }
    ll l=0,r=imax;
    while(l<=r){
        ll mid=(l+r)/2;
        ll t=work(mid);
        if(t>m){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<l;
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...