专栏文章

题解：P9982 [USACO23DEC] Haybale Distribution G

ZZBH_799
P9982题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodwjtm
此快照首次捕获于
2025/12/02 17:37
3 个月前
此快照最后确认于
2025/12/02 17:37
3 个月前
查看原文

题目分析

前置知识：二分、三分
首先，将 xx 从小到大排序。接下来，我们观察当 yy 从 ii 变为 i+1i+1 时答案的变化 Δans\Delta ans。令 pp 表示 a1∼Na_{1 \sim N} 中第一个大于等于 ii 的数的位置，则 Δans=a(p−1)−b(n−p+1)=(a+b)p−a−bn−b\Delta ans=a(p-1)-b(n-p+1)=(a+b)p-a-bn-b。注意到 Δans\Delta ans 单调递增，我们可以知道 ansans 是一个单谷函数，所以我们可以使用二分或三分来求这个谷值。

代码实现

注意整数三分的取整问题。这里推荐使用 r−l>2r-l>2 作为终止条件，以 l=lmidl=lmid 和 r=rmidr=rmid 作为区间取舍操作，并在循环结束后遍历 l∼rl \sim r 以求得答案。

二分 AC code

CPP
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
#define fr first
#define sc second
using ll=long long;
using db=double;
using i128=__int128;

const int N=2e5+5;
int n,a[N];
ll s[N];

ll calc(int cur,int x,int y){
    int pos=lower_bound(a+1,a+n+1,cur)-a;
    return 1ll*x*(1ll*cur*(pos-1)-s[pos-1])+1ll*y*(s[n]-s[pos-1]-1ll*cur*(n-pos+1));
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        int l=0,r=1e6;
        while(l<r){
            int mid=(l+r+1)>>1,pos=lower_bound(a+1,a+n+1,mid)-a;
            ll cur=1ll*x*(pos-1)-1ll*y*(n-pos+1);
            if(cur<=0) l=mid;
            else r=mid-1;
        }
        cout<<min(calc(l,x,y),calc(l+1,x,y))<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--) solve();
    return 0;
}

三分 AC code

CPP
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
#define fr first
#define sc second
using ll=long long;
using db=double;
using i128=__int128;

const int N=2e5+5;
int n,a[N];
ll s[N];

ll calc(int mid,int x,int y){
    int pos=lower_bound(a+1,a+n+1,mid)-a;
    return 1ll*x*(1ll*mid*(pos-1)-s[pos-1])+1ll*y*(s[n]-s[pos-1]-1ll*mid*(n-pos+1));
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        int l=0,r=1e6;
        while(r-l>2){
            int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
            if(calc(lmid,x,y)<=calc(rmid,x,y)) r=rmid;
            else l=lmid;
        }
        ll ans=1e18;
        for(int i=l;i<=r;i++) ans=min(ans,calc(i,x,y));
        cout<<ans<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--) solve();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...