题解 P4264 【[USACO18FEB]Teleportation S】

· · 题解

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

题解

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

废话不多说。

首先问题的本质就是求如果当这个传送门的端点位于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)函数都是一个简单的函数，我们可以推导出以下的玩意：

f(y)=\sum^{n}_{i=1}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;
}