E Byteland, Berland and Disputed Cities

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;
}

最后

以上就是拉长煎蛋为你收集整理的E Byteland, Berland and Disputed Cities的全部内容，希望文章能够帮你解决E Byteland, Berland and Disputed Cities所遇到的程序开发问题。

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