Codeforces 908F New Year and Rainbow Roads

New Year and Rainbow Roads

思路：我们考虑两个绿点之间的红点和蓝点， 首先把这些红点和蓝点接到绿点上面绝对不会超过绿点距离的两倍。

然后我们先把两个绿点连上， 再把绿点经过蓝点到绿点的线连上， 绿点经过红点到绿点的线连上， 这时距离为3倍的绿点间距离，

然后我们可以在第二条路径和第三条路径上断开一段最长的， 和两个的绿点距离取个最小值，就是这段的贡献。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 3e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int n, p, dis[N];

char s[];

vector<int> G, R, B;

int main() {

    scanf("%d", &n);

    for(int i = ; i <= n; i++) {

        scanf("%d%s", &p, s);

        if(s[] == 'G') G.push_back(p);

        else if(s[] == 'R') R.push_back(p);

        else B.push_back(p);

    }

    LL ans = ;

    if(SZ(G)) {

        int S = G[], T = G[SZ(G)-];

        if(SZ(R) && R[] < S) ans += abs(R[] - S);

        if(SZ(R) && R[SZ(R)-] > T) ans += abs(R[SZ(R)-] - T);

        if(SZ(B) && B[] < S) ans += abs(B[] - S);

        if(SZ(B) && B[SZ(B)-] > T) ans += abs(B[SZ(B)-] - T);

        for(int i = ; i +  < SZ(G); i++) {

            LL l = G[i], r = G[i + ];

            LL ret = , tmp1 = INF, tmp2 = INF;

            int x = lower_bound(R.begin(), R.end(), l) - R.begin();

            int y = lower_bound(R.begin(), R.end(), r) - R.begin() - ;

            if(x <= y) {

                tmp1 = min(tmp1, r-l-(R[x]-l));

                tmp1 = min(tmp1, r-l-(r-R[y]));

                for(int j = x; j < y; j++) tmp1 = min(tmp1, r-l-(R[j+]-R[j]));

            } else tmp1 = ;

            x = lower_bound(B.begin(), B.end(), l) - B.begin();

            y = lower_bound(B.begin(), B.end(), r) - B.begin() - ;

            if(x <= y) {

                tmp2 = min(tmp2, r-l-(B[x]-l));

                tmp2 = min(tmp2, r-l-(r-B[y]));

                for(int j = x; j < y; j++) tmp2 = min(tmp2, r-l-(B[j+]-B[j]));

            } else tmp2 = ;

            ans += min( * (r - l), tmp1 + tmp2 + r - l);

        }

    } else {

        if(SZ(R)) ans += R[SZ(R)-] - R[];

        if(SZ(B)) ans += B[SZ(B)-] - B[];

    }

    printf("%lld\n", ans);

    return ;

}

/*

*/