题解：P9982 [USACO23DEC] Haybale Distribution G

· · 题解

题目大意

数轴上有 N 个定点，你需要取一个点，使得这个点到其左边的定点的距离的和的 a 倍加上这个点到其右边的定点的距离的和的 b 倍最小。

思路分析

简单数学题。

假设我们现在第 p 定点到第 p+1 个定点之间，往右移动一个单位对答案造成的影响就是

ap-b(n-p)

而这个值是答案在整数域上的“微分”，因此，当它从负变成正时，答案可以取到最值。

令

ap-b(n-p)\le0 ap-bn+bp\le0 (a+b)p\le bn

因为 a>0，b>0，所以 a+b>0。则

p\le\frac{bn}{a+b}

因为从第 p 个定点到第 p+1 个定点的过程中，变化依旧是负的，所以我们将 y 设在第 p+1 个定点上，就有最小值。

计算答案则用前缀和优化一下即可。
时间复杂度 O(q+n\log n)。

Talk is cheap,show me the code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=2e5+5;
int n,q,x[N],sum[N][2];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i];
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++)sum[i][0]=sum[i-1][0]+x[n]-x[i]+1;
    for(int i=n;i>=1;i--)sum[i][1]=sum[i+1][1]+x[i]-x[1]+1;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        int p=b*n/(a+b)+1;
        cout<<(sum[p][0]-p*(x[n]-x[p]+1))*a+(sum[p][1]-(n-p+1)*(x[p]-x[1]+1))*b<<'\n';
    }

    return 0;
}