E Byteland, Berland and Disputed Cities
题意:给你1,2,3,三种点,使其排列在x轴上,去掉点1后使其2,3点完全联通,去掉点2后使其1,3点完全联通,问最短需要多长。
思路:1和2两个点不用连,连了也得去掉。
那么如果只有一个3点,我们把3点看成1点,按顺序连一遍即可,同样2点也是如此。
如果有两个3点,那么第一个3点的最左面相同点挨着连即可,第二个3点的最右面也是如此,但是两个3点的中间只有两种连法,(1)从左面的3点出发连接中间的1点直到右面的3点+从左面的3点出发连接中间的2点直到右面的3点(2)两个3点直接连接+(从左面的3点出发连接中间的1点直到右面的3点-从左面的3点出发连接中间的1点直到右面的3点中的最大差值)+(从左面的3点出发连接中间的2点直到右面的3点-从左面的3点出发连接中间的2点直到右面的3点中的最大差值)。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=0x3f3f3f3f;
const int maxn=200005;
int n;
int br,bb,bp;
int main()
{while(~scanf("%d",&n)){int index;char c;ll ans=0;br=bb=bp=0;int lr,lb,lp;int maxr=0,maxb=0;for(int i=0; i<n; i++){scanf("%d %c",&index,&c);//cout<<c<<endl;if(c=='P'||c=='R'){if(br){ans+=(index-lr);maxr=max(maxr,index-lr);}lr=index;br=1;}//printf("ans=%dn",ans);if(c=='P'||c=='B'){if(bb){ans+=(index-lb);maxb=max(maxb,index-lb);}lb=index;bb=1;}//printf("ans=%dn",ans);if(c=='P'){if(bp){ans+=min(0,index-lp-maxr-maxb);}maxr=0,maxb=0;lp=index;bp=1;}//printf("ans=%dn",ans);}printf("%lldn",ans);}return 0;
}
本文发布于:2024-02-03 23:29:51,感谢您对本站的认可!
本文链接:https://www.4u4v.net/it/170697560451586.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |