Codeforces 962E Byteland, Berland and Disputed Cities [想法]

Codeforces 962E Byteland, Berland and Disputed Cities [想法]

题意：给你在一维坐标的三种城市R,B,P，连接总和最短的边，使得只看城市RP或者只看城市BP，都要是相互连通的。

题解：分类讨论：

①假如没有P，那么就是B与B相连，R与R相连。

②假如只有BP，那么当看RP的时候，P是需要连通的，只有RP的时候同理。对于这种情况因此首先我们让P先全部连通，然后我们再对于两个相邻的p，找到中间的B或R，使得前一段B连接第一个P，后一段B连接第二个p，答案的最优解枚举即可得。

③RBP均存在，我们可以先按照②分别对RB做一次答案，对于两个相邻的P之间的R与B的答案是pi-pi-1+ansR+ansB,这时候可能存在另一种方案，就是将PBP，PRP依次连接，答案是2*（pi-pi-1），因此我们的答案是min(pi-pi-1+ansR,ansB,2*(pi-pi-1)。

AC代码：

#include<stdio.h>
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
vector<ll>vt[3];
ll ANS1[200005];
int main()
{ll n,R=0,B=0,P=0,k,mi,ma; scanf("%lld",&n);vt[0].push_back(-4000000001ll);vt[1].push_back(-4000000001ll);vt[2].push_back(-4000000001ll);for(ll i=0;i<n;i++){char s[2];scanf("%lld%s",&k,s);if(s[0]=='R')R++,vt[0].push_back(k);if(s[0]=='B')B++,vt[1].push_back(k);if(s[0]=='P')P++,vt[2].push_back(k);if(i==0)mi=ma=k;mi=min(mi,k);ma=max(ma,k);}vt[0].push_back(4000000001ll);vt[1].push_back(4000000001ll);vt[2].push_back(4000000001ll);if(R==n||B==n){printf("%lldn",ma-mi);return 0;}if(P==0){printf("%lldn",vt[0][vt[0].size()-2]-vt[0][1]+vt[1][vt[1].size()-2]-vt[1][1]);return 0;} ll ans=0;for(int t=0;t<2;t++){ll now=0,fin=0;for(ll i=1;i<vt[2].size();i++){ll sum=0,ok;while(vt[t][fin+1]<vt[2][i]){fin++;sum+=vt[t][fin]-max(vt[2][i-1],vt[t][fin-1]);}ok=sum;for(ll j=fin;j>now;j--){sum=sum-(vt[t][j]-max(vt[2][i-1],vt[t][j-1]))+(min(vt[2][i],vt[t][j+1])-vt[t][j]);ok=min(ok,sum);}if(t==0)ANS1[i]=ok;else {if(vt[2][i]!=4000000001ll&&vt[2][i-1]!=-4000000001ll)ans+=min(ANS1[i]+ok+vt[2][i]-vt[2][i-1],2*(vt[2][i]-vt[2][i-1]));else ans+=ANS1[i]+ok;}now=fin;}} printf("%lldn",ans);
}