题解 P4264 【[USACO18FEB]Teleportation S】

· · 题解

题目传输门

简单介绍一下题目意思：

他经过良心发现，决定在$x=0$的地方建造一个垃圾回收站，你的任务是确定一个最优的点$y$，使得他可以通过传输门或直接走到$b$地的最大值 通过观察，我们可以发现，有一些点是永远都是不可能走传输门的。 ~~这些点的条件是什么呢~~ **$abs(a)>abs(a-b)$** 满足这个条件的两个点，我们可以直接把$abs(a-b)$的值加入$ans$值 我们可以设$f(x)$表示的是第$x$个点变化的规律 结果发现$f(x)$变化规律是一个很有规律~~其实没有~~的函数图像 ### 此时，就来到了这道题最难的部分 其实，这个函数有三个交接点，我们只要用一个差分去维护这个函数图像就行了 那么，三个交接点是哪三个呢 #### 其实是$a-b$ , $b$ , $a+b

当交接点为a-b时，斜率为-1

当交接点为b时，斜率为2

当交接点为a+b时，斜率为-1

然后，就用一个map维护函数图像的交接点就行了

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    bool f=0;
    char c=getchar();
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
void write(int x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n;
int ans;
int sum;
map<int,int> mp;
int minn;
int k;
int l;
signed main(){
    n=read();
    for(register int i=1;i<=n;++i)
        {
            int x;
            int y;
            x=read();
            y=read();
            ans+=abs(x-y);
            if(abs(x)<=abs(x-y))//初始化三个交接点
                {
                    mp[y]+=2;
                    mp[y-abs(x-y)+abs(x)]--;
                    mp[y+abs(x-y)-abs(x)]--; 
                }
        }
    minn=ans;
    l=-100000000;
    map<int,int>::iterator i;
    for(i=mp.begin();i!=mp.end();++i)//分别枚举三个交接点
        {
            int y=i->first;
            int h=i->second;
            minn+=sum*(y-l);
            l=y;
            sum+=h;
            ans=min(ans,minn);
        }
    write(ans);//输出
    return 0;
}

最后，祝大家AC此题