题解：P9982 [USACO23DEC] Haybale Distribution G

ZBH_799 · 2025-08-11 21:30:10 · 题解

题目分析

前置知识：二分、三分

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

代码实现

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

二分 AC code

#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

#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;
}