http://codeforces.com/contest/750/problem/C
题意：有n场比赛，每场比赛有一个c，代表比赛结束后分数的增长情况，有一个d，代表这场比赛在div1或者div2打。div1 >= 1900，div2 < 1900。求打完这n场比赛后可能得到的最大分数。如果无限大就输出“Inifinity”，如果有矛盾就输出“Impossible”。
思路：官方题解。
For every contest we know that the current rating is x increased by some prefix sum of c_i (changes of rating). If Limak is in the division 1, we have inequality x+prefSum >= 1900 so we have x >= 1900-prefSum. If Limak is in the division 2, we have inequality x_prefSum <= 1899 so it is x <= 1899-prefSum. From this set of inequalities, your task is to find the biggest x satisfying all of them.
设立一个可行的上下限，对每场比赛，更新上下限。设一个初始分数 x，-INF <= X <= INF，处理一个c[i]的前缀和s，如果在div1打的话，只有 x + s >= 1900，才可在div1打，那么分数的下限就是max（low，1900 - s），如果在div2打，只有 x + s <= 1899，才可以才div2打，那么分数的上限是min（high，1899 - s）。最后处理答案，如果一直在div1打，那么分数无穷大，如果 low 和 high 冲突，那么是不可能。否则就是初始的分数上限 + 前缀和s。
昨晚大概也想的是设立一个上下限，但是想的好乱，搞不定。还是要多训练自己的思维能力。
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <queue> 8 #include <vector> 9 #include <map> 10 #include <set> 11 using namespace std; 12 #define INF 0x3f3f3f3f 13 #define N 200010 14 typedef long long LL; 15 int n, c[N], d[N]; 16 17 int main() { 18 cin >> n; 19 int flag = 1; 20 for(int i = 1; i <= n; i++) 21 scanf("%d%d", &c[i], &d[i]); 22 int left = -INF, right = INF; 23 int s = 0; 24 for(int i = 1; i <= n; i++) { 25 if(d[i] == 1) left = max(left, 1900 - s); 26 if(d[i] == 2) right = min(right, 1899 - s); 27 s += c[i]; 28 } 29 if(right < left) puts("Impossible"); 30 else if(right == INF) puts("Infinity"); 31 else printf("%d ", right + s); 32 return 0; 33 }