[KOI 2021 Round 2] 累计距离

· · 题解

题意

数轴上有 N 个村庄，每个村庄位于位置 x_i，有 a_i 个居民。对于每个查询位置 q_i，计算所有居民到 q_j 的累计距离 f(q_j) = \sum_{i=1}^N a_i \times |x_i - q_j|。

分析

根据绝对值的性质，可以得到两种情况：

累计距离可拆分为两部分计算：

f(q) = \sum_{x_i \leq q} a_i (q - x_i) + \sum_{x_i > q} a_i (x_i - q)

预处理这两部分的前缀和，就能快速计算累计距离，所以接下来我们就来预处理一下这两个部分。

首先将村庄按位置 x_i 升序排序。排序后，所有村庄的位置形成有序序列，便于后续二分查找分割点。

定义数组 suma，suma_k 表示前 k 个村庄的居民总数。再定义数组数组 sumxa，sumxa_k 表示前 k 个村庄的 a_i x_i 总和。

接下来用二分查找分割点，使用二分查找找到第一个满足 x_i \geq q 的村庄下标 k。此时前 k 个村庄的位置均 < q，如果 x_k = q，则包含在左边或右边都行。从 k 到 N-1 的村庄位置均 \geq q。

于是我们可以累计距离啦，分左右分别计算，左边有 k 个村庄，右边有 N-k 个村庄。最后把左右两边的距离加起来就行了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,k;
ll o,l,r;
struct D{
    ll x,a;
    bool operator<(const D&w)const{return x<w.x;}
};
int main() {
    ios::sync_with_stdio(false);//快读快写启动，我怕炸TLE
    cin.tie(nullptr); 
    cin>>n>>q;
    vector<D> v(n);
    for(int i=0;i<n;i++) cin>>v[i].a>>v[i].x;
    sort(v.begin(),v.end());
    vector<ll> suma(n+1,0);//前i个村庄的a总和
    vector<ll> sumax(n+1,0);//前i个村庄的a*x总和
    for(int i=0;i<n;i++){
        suma[i+1]=suma[i]+v[i].a;
        sumax[i+1]=sumax[i]+v[i].a*v[i].x;
    }
    for (int i=0;i<q;i++){
        cin>>o;
        k=lower_bound(v.begin(),v.end(),D{o,0})-v.begin();//二分查找第一个x>=q的村庄下标
        l=o*suma[k]-sumax[k];//左边的距离
        r=(sumax[n]-sumax[k])-o*(suma[n]-suma[k]);//右边的距离
        cout<<l+r<<endl;
    }
    return 0;
}