http://codeforces.com/contest/750/problem/C

反正我不会这道题。。。为什么那么多人做出来了。。。我好菜.jpg

 

题目大意:cf每个人都有分数,每次都会在div2(<=1899)或者div1(>=1900)打比赛。有n个输入,每次输入ci和di,ci表示打了该场比赛以后的得分,di表示打的是div1还是div2,问,最后那个人可能得到的最高的分数是多少?

 

思路:

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。

然后我们可以发现,最后的解是在[1900-presum,1899-presum]之间。

 

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include 
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = 200000 + 5;
const int inf = 1e8;
int n;

int main(){
    cin >> n;
    int lb = -inf, rb = inf;
    int tmp = 0;
    for (int i = 1; i <= n; i++){
        int c, d; scanf("%d%d", &c, &d);
        if (d == 1){
            lb = max(lb, 1900 - tmp);
        }
        else {
            rb = min(rb, 1899 - tmp);
        }
        tmp += c;
    }
    if (rb == inf){
        printf("Infinity\n");
        return 0;
    }
    if (lb > rb) {
        printf("Impossible\n");
        return 0;
    }
    printf("%d\n", rb + tmp);
    return 0;
}
View Code