Good Bye 2016 - C-白红宇

Good Bye 2016 - C

阅读量：6982 次

发布时间：2019-06-27

本文共 1763 字，大约阅读时间需要 5 分钟。

题目链接：http://codeforces.com/contest/750/problem/C

题意：在CF中，每个人都有个Rank值。当Rank>=1900时，为DIV1。Rank<1900时，为DIV2。现在给你参加每一场的DIV值和参加完这一层后的Rank值变化。问最大可能的初始Rank值。如果答案无限大输出Infinity,如果不可能出现输入的情况输出impossible。其他情况输出可能的最大答案。

思路：二分初始Rank值，然后在二分出来的初始Rank值在计算过程中发现分值在DIV1但是输入为DIV2表示初始分值高了，否则低了。

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long int LL;const int MAXN = 2e5 + 10;const int INF = 2e8;struct Node{ int c, d;}Contest[MAXN];bool check(int x, int n){ LL Rank = x; for (int i = 0; i < n; i++){ if (Rank >= 1900 && Contest[i].d == 2){ //高了 return true; } else if (Rank<1900 && Contest[i].d == 1){ //低了 return false; } else{ Rank += Contest[i].c; } } return false;}int main(){ //#ifdef kirito // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); //#endif // int start = clock(); int n; while (scanf("%d", &n) != EOF){ for (int i = 0; i < n; i++){ scanf("%d%d", &Contest[i].c, &Contest[i].d); } int L = -INF, R = INF, mid; while (R >= L) { mid = (L + R) >> 1; if (check(mid, n)){ R = mid - 1; } else{ L = mid + 1; } } if (R == INF){ printf("Infinity\n"); } else{ LL ans = R; bool flag = true; for (int i = 0; i < n; i++){ //最后再判一遍是否与输入合法 if (ans >= 1900 && Contest[i].d == 2){ flag = false; } else if (ans<1900 && Contest[i].d == 1){ flag = false; } else{ ans += Contest[i].c; } } if (flag){ printf("%I64d\n", ans); } else{ printf("Impossible\n"); } } } //#ifdef LOCAL_TIME // cout << "[Finished in " << clock() - start << " ms]" << endl; //#endif return 0;}

转载于:https://www.cnblogs.com/kirito520/p/6238970.html

你可能感兴趣的文章