自动搬运

查看原文

来自洛谷，原作者为

	xuanxuan001 生活就像愤怒的小鸟，失败后总有几只猪在笑。

搬运于2025-08-24 22:18:04，当前版本为作者最后更新于2022-08-22 22:55:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

打 ARC 的时候做了这题，赛后知道洛谷上有这道原题，不得不说AT官方题解的做法是真的妙，所以就讲讲我赛时的贪心做法吧(???)。

先推个式子，首先把 $x$ 按升序排序，那么有

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n|x_i - x_j|=2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nx_j - x_i $$

先抛掉前面那个那个 2，然后考虑每个 x 被算了多少次，转化为

$$\sum\limits_{i=1}^n(n-i-(i-1))x_i=\sum\limits_{i=1}^n(-2i+n+1)x_i $$

也就是说，第 $i$ 个人（按 $x$ 递增排序后的）的位置会给答案带来一个 $2i-n-1$ 的贡献，所以要让前一半的人尽量靠后，后一半人尽量靠前，于是考虑贪心。

最开始一定是让所有人尽量靠后，所以直到遇到某个人的右端点了再把他放下。

考虑将所有的 $l$ 值和 $r$ 值放到一起离散化，然后维护扫描线，对于当前扫描到的位置 $p$，记 $vl_p$ 表示以 $p$ 为左端点的人的数量，$vr_p$ 表示以 $p$ 为右端点的人的数量，$lst$ 为目前确定位置的人的数量，$cnt$ 为左端点在 $p$ 以及 $p$ 之前的人的数量。

那么首先 $cnt \leftarrow cnt + vl_p$，$ans \leftarrow ans + p \sum\limits_{i=lst+1}^{lst+vr_p}(2i-n-1)$，$lst \leftarrow lst + vr_p$，这几步应该不用多说，就是更新 $lst,cnt$，然后更新放在这里的答案，因为右端点就在 $p$ 上的只能放在这上面了。

然后接下来就是比较关键的一步了，就是如果 $cnt+lst \ge n+1$，那么就意味着把目前挂在手上的这 $cnt-lst$ 个人再往后放一个位置对答案的贡献开始增加，否则就是会减少。所以如果发现 $cnt+lst \ge n+1$ 了，那么就将现在挂着的人全部放在 $p$ 上，而再后面的人一定都是后半段了，它们要尽量靠前，所以都取左端点计算答案即可。

感觉整篇题解写的挺草率的，也不知道讲没讲明白，欢迎各位指正。

代码：

#include<cstdio>
#include<algorithm>
#define TY ll
#define MAXN 300002
#define debug if( 1 &&putchar('>'))
#define FOR(i,a,b) for(TY i=(a);i<=(b);++i)
#define fOR(i,a,b) for(TY i=(a);i<(b);++i)
#define ROF(i,a,b) for(TY i=(a);i>=(b);--i)
#define rOF(i,a,b) for(TY i=(a);i>(b);--i)
using namespace std;
typedef long long ll;
const TY M=998244353;
typedef unsigned long long ull;
TY _abs(TY a){return a<0?-a:a;}
TY maxn(TY a,TY b){return a>b?a:b;}
TY minn(TY a,TY b){return a<b?a:b;}
TY gcd(TY a,TY b){return b?gcd(b,a%b):a;}
TY qp(TY a,TY b){TY ans=1;do{if(b&1)ans=ans*a%M;a=a*a%M;}while(b>>=1);return ans;}
char getc(){char ch=getchar();while(ch==' '||ch=='\n')ch=getchar();return ch;}
TY qr(){
	char ch=getchar();TY s=0,x=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')x=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0';return x*s;
}void qw(TY a,char ch){
	if(a<0){a=-a;putchar('-');}
	if(a>9)qw(a/10,0);putchar(a%10+'0');
	if(ch)putchar(ch);
}TY n=qr(),m,l[MAXN],r[MAXN],b[MAXN<<1],ans,cnt,lst,vl[MAXN<<1],vr[MAXN<<1];
inline TY js(TY x,TY y){return (y-x)*(x+y-n);}
//将(lst,cnt]的人放在某个位置的权值和，其实循环计算也可以
int main(){
	FOR(i,1,n){b[i*2-1]=l[i]=qr();b[i<<1]=r[i]=qr();}
	sort(b+1,b+(n<<1|1));m=unique(b+1,b+(n<<1|1))-b-1;
	FOR(i,1,n){
		++vl[l[i]=lower_bound(b+1,b+m+1,l[i])-b];
		++vr[r[i]=lower_bound(b+1,b+m+1,r[i])-b];//预处理一些数组
	}FOR(i,1,m){
		cnt+=vl[i];
		if(lst+vr[i]+cnt>n){//如果开始转变为后半段
			ans+=b[i]*js(lst,cnt);
			FOR(j,i+1,m)fOR(k,0,vl[j])
				ans+=((++cnt)*2-n-1)*b[j];//将后面的全部取左端点
			break;//考虑完直接退出
		}fOR(j,0,vr[i])ans+=((++lst)*2-n-1)*b[i];//更新lst
	}qw(ans,0);
	return 0;
}