【CF962E】Byteland, Berland and Disputed Cities

Portal！ --->

几句话题意

　　数轴上面有三种点（B点，R点，P点），现在要将其中的某些点连起来，满足将所有B点去掉之后，所有P点和R点都连通&将所有R点去掉之后，所有B点和P点都连通两个条件，连接两点的代价为数轴上距离，求最小代价（读入按照数轴上位置从小到大的顺序）

---

Solution

　　这题。。其实是个特别神秘的贪心

　　首先有个特别直接的想法，就是。。所有的B点和它的前一个B点或者P点连，所有的R点和它的前一个R点或者P点连，P点和前一个R点和前一个B点连，这样就一定能保证满足那两个条件并且不会绕多太多路

　　但是，画一下图会发现，其实还有一种连法是将一个P点和它的前一个P点连起来，这样这两个P点之间就可以省掉两条边（B与B连的一条，R与R连的一条）弱弱的我一开始完全没想到这个Q^Q

　　那么最优解应该就是在这两种情况中取较小的那个就好了

　　

　　具体实现的话，因为保证读入是按顺序的，那就一开始先全部按照第一种方法连，如果当前有两个P点那么就与第二种连法取最优解就好了，中间稍微记录一下边的最大值即可

　　代码大概长这个样子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=2*(1e5)+10,inf=2147483647;
ll ans;
int n,lastR,lastB,lastP,mxR,mxB;

int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
#endif
    int x;
    char c;
    scanf("%d",&n);
    lastR=lastB=lastP=-inf;
    mxR=mxB=0;
    for (int i=1;i<=n;++i){
        scanf("%d %cn",&x,&c);
        if (c=='R'||c=='P'){
            if (lastR!=-inf) 
                ans+=x-lastR,mxR=max(mxR,x-lastR);
            lastR=x; 
        }
        if (c=='B'||c=='P'){
            if (lastB!=-inf)
                ans+=x-lastB,mxB=max(mxB,x-lastB);
            lastB=x;
        }
        if (c=='P'){
            if (lastP!=-inf)
                ans+=min(0,x-lastP-mxR-mxB);
            lastP=x; mxR=mxB=0;
        }
    }
    printf("%I64dn",ans);
}