CF962E- Byteland, Berland and Disputed Cities （贪心）

题意:让你给点连线，再去除所有R点，或B点后都可以实现任意两点互相可达，并且代价最小，两点连线的代码为两点间的距离

题解：我只需要当到达P点的时候要么与前一个p点相连3次然后减取之前R点B点的最大两点距离，或者就直接与前面一个点连接两次取两者最小值即可，其他情况直接与前面一个点相连即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<stack>
#include<bitset>
using namespace std;
#define mes(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(i = a; i <= b; i++)
#define dec(i,a,b) for(i = b; i >= a; i--)
#define fi first
#define se second
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,L,mid
#define rson rs,mid+1,R
typedef double db;
typedef long long int ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const ll inf = 1e15;
const int mx = 2e5+5;
const int x_move[] = {1,-1,0,0,1,1,-1,-1};
const int y_move[] = {0,0,1,-1,1,-1,1,-1};
int main(){
	int t,q,ca = 1;
	int n;
	ll pa,pb,pc;
	ll ans = 0;
	pa = pb = pc = inf;
	ll pra = 0,prb = 0;
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		ll v;
		char str[10];
		scanf("%I64d%s",&v,str);
		if(str[0]=='R'){
			if(pa!=inf){
				pra = max(pra,v-pa);
				ans += v-pa;
			}
			pa = v;
		}
		else if(str[0]=='B'){
			if(pb!=inf){
				prb = max(prb,v-pb);
				ans += v-pb;
			}
			pb = v;
		}
		else{
			if(pb!=inf){
				prb = max(prb,v-pb);
				ans += v-pb;
			}
			if(pa!=inf){
				pra = max(pra,v-pa);
				ans += v-pa;
			}
			if(pc!=inf)
				ans = min(ans,ans+v-pc-pra-prb);
			pa = pb = pc = v;
			pra = prb = 0;
		}
	}
	printf("%I64dn",ans);
	return 0;
}

最后

以上就是喜悦铃铛为你收集整理的CF962E- Byteland, Berland and Disputed Cities （贪心）的全部内容，希望文章能够帮你解决CF962E- Byteland, Berland and Disputed Cities （贪心）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。