【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 %c\n",&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("%I64d\n",ans);

}