【CF962E】Byteland, Berland and Disputed Cities

【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_JUDGEfreopen("a.in","r",stdin);
#endifint 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);
}

转载于:.html