自动搬运

查看原文

来自洛谷，原作者为

	Ghosty_Neutrino ♬ Just do it！♬

搬运于2025-08-24 23:17:44，当前版本为作者最后更新于2025-06-08 22:12:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

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

分析

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

• 当 $x_i \leq q$ 时，$|x_i - q| = q - x_i$。
• 当 $x_i > q$ 时，$|x_i - q| = x_i - q$。

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

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