Codefroces 750C：New Year and Rating（思维）-白红宇

Codefroces 750C：New Year and Rating（思维）

阅读量：5243 次

发布时间：2019-06-14

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

题意：有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 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #include 
              
               11 using namespace std;12 #define INF 0x3f3f3f3f13 #define N 20001014 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\n", right + s);32 return 0;33 }

转载于:https://www.cnblogs.com/fightfordream/p/6239274.html

你可能感兴趣的文章