思路：
http://codeforces.com/blog/entry/58869。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int MAXN = 200005; 5 int t[MAXN], n; 6 char c[MAXN]; 7 int get_sum(int i, vector<int> & v, char color) 8 { 9 int maxn = 0, last = v[i]; 10 for (int j = v[i] + 1; j <= v[i + 1]; j++) 11 { 12 if (c[j] == color || c[j] == 'P') 13 { 14 if (t[j] - t[last] > maxn) maxn = t[j] - t[last]; 15 last = j; 16 } 17 } 18 return last == v[i] ? 0 : t[v[i + 1]] - t[v[i]] - maxn; 19 } 20 int main() 21 { 22 while (cin >> n) 23 { 24 int p_start = -1, p_end = -1, r_start = -1, r_end = -1, b_start = -1, b_end = -1; 25 vector<int> v; 26 for (int i = 0; i < n; i++) 27 { 28 cin >> t[i] >> c[i]; 29 if (c[i] == 'P') 30 { 31 p_end = i; 32 if (p_start == -1) p_start = i; 33 v.push_back(i); 34 } 35 else if (c[i] == 'R') 36 { 37 r_end = i; 38 if (r_start == -1) r_start = i; 39 } 40 else 41 { 42 b_end = i; 43 if (b_start == -1) b_start = i; 44 } 45 } 46 ll ans = 0; 47 if (p_start == -1) 48 { 49 if (r_start != -1) ans += t[r_end] - t[r_start]; 50 if (b_start != -1) ans += t[b_end] - t[b_start]; 51 cout << ans << endl; 52 continue; 53 } 54 if (r_start != -1) 55 { 56 if (r_start < p_start) ans += t[p_start] - t[r_start]; 57 if (r_end > p_end) ans += t[r_end] - t[p_end]; 58 } 59 if (b_start != -1) 60 { 61 if (b_start < p_start) ans += t[p_start] - t[b_start]; 62 if (b_end > p_end) ans += t[b_end] - t[p_end]; 63 } 64 for (int i = 0; i < v.size() - 1; i++) 65 { 66 int tmp_R = get_sum(i, v, 'R'), tmp_B = get_sum(i, v, 'B'); 67 if (!tmp_R && !tmp_B) { ans += t[v[i + 1]] - t[v[i]]; continue; } 68 int minn = 2 * (t[v[i + 1]] - t[v[i]]); 69 int tmp = tmp_R + tmp_B + t[v[i + 1]] - t[v[i]]; 70 minn = min(minn, tmp); 71 ans += minn; 72 } 73 cout << ans << endl; 74 } 75 return 0; 76 }