F. New Year and Rainbow Roads
GoodBye2017 F题。
最后一分钟被绝杀,被手速坑了。。。
容易发现,R,B都必须与G相连,分下面三种情况
1.对于在最左边G的左边的点,一定会连这个G
2.那么也就是在某两个G中间,求得如何连接使得两个黑点(经过R,B )花费最小
3.对于在最右边G的右边的点,一定会连这个G
1 3 很简单,考虑2,有下面几种情况:
1.两个G中间没有RB,那么连接两个G就好了。
2.两个G中间有R,那么必须连接两个G,然后把R分为两段,左边的一段与左边的G相连,右边的一段与右边的G相连。
3.两个G中间有B,与2同理
4.两个G中间有B R,那么可以把 区间里的B和R分别串在一起,再与G相连,或者像上面那样找出分割点,然后分别与G相连,那么求得这两个值得最小值就好了。
另外 ,还要特判没有G得情况,直接就是RB得链长和
c++代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<queue> #include<stack> #include<map> #include<cctype> #include<set> #include<string> #include<iostream> #include<algorithm> #include<string> #define eps 1e-9 #define mp make_pair #define lowbit(x) (x & (-x)) #define random(l,r) (rand()%(r - l + 1) + l) #define size(a) ((int) a.size()) #define rep(i,x,y) for(register int i = x;i <= y;++i) #define repd(i,x,y) for(register int i = x;i >= y;--i) using namespace std; typedef long long ll; template<typename T>void read(T&x) { x = 0;char c;int sign = 1; do { c = getchar();if(c == '-') sign = -1; }while(!isdigit(c)); do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c)); x *= sign; } const int N = 3e5 + 500; int n,cnt;ll ans; char c; struct Str { ll pos; int k; } num[N]; int main() { read(n); rep(i,1,n) { read(num[++cnt].pos); do { c = getchar(); }while(c != 'G' && c != 'B' && c != 'R'); if(c == 'G') num[cnt].k = 1; else if(c == 'B') num[cnt].k = 2; else if(c == 'R') num[cnt].k = 3; } int l=0,r=0; rep(i,1,cnt) if(num[i].k == 1) { l = i;break; } repd(i,cnt,1) if(num[i].k == 1) { r = i;break; } if(l == r && r == 0) { rep(i,1,cnt) if(num[i].k == 2) { l = i;break; } repd(i,cnt,1) if(num[i].k == 2) { r = i;break; } ans = num[r].pos - num[l].pos; l = 0,r = 0; rep(i,1,cnt) if(num[i].k == 3) { l = i;break; } repd(i,cnt,1) if(num[i].k == 3) { r = i;break; } ans += num[r].pos - num[l].pos; printf("%I64d\n",ans); return 0; } rep(i,1,l - 1) if(num[i].k == 2) { ans += num[l].pos - num[i].pos;break; } rep(i,1,l - 1) if(num[i].k == 3) { ans += num[l].pos - num[i].pos;break; } repd(i,cnt,r + 1) if(num[i].k == 2) { ans += num[i].pos - num[r].pos; break; } repd(i,cnt,r + 1) if(num[i].k == 3) { ans += num[i].pos - num[r].pos; break; } rep(i,l,r) { int j = i + 1; while(num[j].k != 1 && j <= r) ++j; if(j > r) break; ll p1 = 0,p2 = 0,lst1 = i,lst2 = i; bool e1 = 0,e2; rep(q,i + 1,j) if(num[q].k == 2) e1 = 1,p1 = max(p1,num[q].pos - num[lst1].pos),lst1 = q; else if(num[q].k == 3) e2 = 1,p2 = max(p2,num[q].pos - num[lst2].pos),lst2 = q; if(e1 || e2) ans += min((e1?(num[j].pos - num[i].pos - max(p1,num[j].pos - num[lst1].pos)) : 0)+ (e2?(num[j].pos - num[i].pos - max(p2,num[j].pos - num[lst2].pos)) : 0) + (num[j].pos - num[i].pos) , 2 * (num[j].pos - num[i].pos)); else ans += num[j].pos - num[i].pos; i = j - 1; } cout << ans <<endl; return 0; } |