自动搬运

查看原文

来自洛谷，原作者为

	mulberror 把回忆远远的放逐，流星划过寂夜里的深处，碎梦沉沦在眼前起舞。

搬运于2025-08-24 21:58:19，当前版本为作者最后更新于2019-03-02 22:56:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

安利一下自己博客园博客：传送门

题解

先吐槽一波题目：便便传送门，出题人还真的有一点厉害的滑稽。

废话不多说。

首先问题的本质就是求如果当这个传送门的端点位于$y$的时候，最小的求出总代价，我们设为函数$f(y)$。

因为这个$f(y)$是一个具有分段线性的结构函数，我们就在求$f(y)$的时候遍历$y$，就可以了。每次当我们处理到两段函数的交界处时，我们就算出两个函数的斜率，算出其中的最小值。

因为有$n$个点，那么复杂度就是$O(n)$，但是一开始我们的各个点的顺序不定，那么我们需要花$O(nlogn)$的时间来进行排序，然后在用$O(n)$的时间遍历计算$f(y)$。

以上的算法比较的简单，但是我们需要用数学计算出每一个交接点的位置就是$y$的值，以及斜率多少和在每一个交接点的变化。

其中$f_i(y)=min(|a_i-b_i|,|a_i-0|+|b_i-y|)$，表示只用于传送门的代价（第一部分表示直接移动，第二个部分表示如果使用传送门），每一个$f_i(y)$函数都是一个简单的函数，我们可以推导出以下的玩意：

对于交接点，每一个函数对最终的答案都是有贡献的，例如如果$|a_i|≥|a_i-b_i|$，那么就说明$f_i(y)$中没有交接点，那么答案就是讲$f_i(y)$向上平移$|a_i-b_i|$。

对于图片中另外一种情况，如果$a_i<0$并且$a_i≥b_i$，那么就说明$f_i$有三个交接点，那么这个贡献的计算就是：当$y=0$时，$f_i(y)$的斜率$-1$，在$y=b$时$+2$，在$y=2b$时$-1$。

可以选择用$map$映射存储$f(y)$函数在各个交接点出的斜率的变化，然后再按照$y$的顺序遍历就可以得到答案了。

ac代码

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <ctype.h>
# include <iostream>
# include <cmath>
# include <map>
# define LL long long
# define ms(a,b) memset(a,b,sizeof(a))
# define ri (register int)
# define inf (0x7f7f7f7f)
# define pb push_back
# define fi first
# define se second
# define pii pair<int,int>
using namespace std;
inline int gi(){
    int w=0,x=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}
int n;
map<int,int>mp;
LL x=0,y=-inf,s=0;
int main(){
	n=gi();
	for (int i=1;i<=n;i++){
		int a=gi(),b=gi();
		x+=abs(a-b);
		if (abs(a)>abs(a-b)) continue;
		mp[b]+=2;
		if ((a<b&&a<0)||(a>=b&&a>=0)) mp[0]--,mp[2*b]--;
		if ((a<b&&a>=0)||(a>=b&&a<0)) mp[2*b-2*a]--,mp[2*a]--;
	}
	LL ans=x;
	map<int,int>::iterator it;
	for (it=mp.begin();it!=mp.end();it++){
		int ny=it->fi,tmp=it->se;
		x+=s*(ny-y); y=ny; s+=tmp;
		ans=min(ans,x);
	}
	printf("%lld\n",ans);
	return 0;
}