题解 P9982

· · 题解

题意：

给定一些点数轴上的整点 x_i 和 a,b，调整 y 并最小化下式：

\sum_{i=1}^n \begin{cases}a\cdot (y-x_i) & \text{if} \ y>x_i \\ b\cdot(x_i-y)&\text{if}\ x_i>y\end{cases}

思路：

不难观察到原式单谷，关键是怎么证。

考虑最优解的点，设其左侧有 p 个谷仓，右侧有 q 个谷仓，自身位置有 k 个谷仓。右移一个单位长度的贡献是 (p+k)\cdot a-q\cdot b。左移一个单位长度的贡献是 (q+k)\cdot b-p\cdot a。

显然，这两个值必然是正的。

考虑不断向左或向右移动，对于上述两个式子，每次经过谷仓后，第一项的系数会不断增加，第二项的系数会不断下降。即：贡献只会单调上升。

初始化每个位置左右的谷仓距离之和，对于每个点我们可以 O(1) 计算该位置的分数。二分或三分找最低点即可。

复杂度 O(m+q\log m)。

程序如下：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=2e5+5,M=1e6+5;
long long n,q,a,b,x[N],pre[M],pos[M];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&x[i]),x[i]++;
    sort(x+1,x+n+1);
    int fr=0,cur=1;
    for(int i=1;i<=x[n];i++){
        pre[i]=pre[i-1]+fr;
        while(x[cur]==i)cur++,fr++;
    }
    fr=0,cur=n;
    for(int i=x[n];i>=1;i--){
        pos[i]=pos[i+1]+fr;
        while(x[cur]==i)cur--,fr++;
    }
    pre[0]=pre[x[n]+1]=1e9;
    pos[0]=pos[x[n]+1]=1e9;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&a,&b);
        long long l=1,r=x[n],ans;
        while(l<r){
            int mid=(l+r)>>1;
            long long curans=pre[mid]*a+pos[mid]*b;
            long long nxtans=pre[mid+1]*a+pos[mid+1]*b;
            if(nxtans<curans)l=mid+1;
            else r=mid;
        }
        printf("%lld\n",pre[l]*a+pos[l]*b);
    }
    return 0;
}

THE END

USACO 2024 Dec RP++.