Good Bye 2016 C. New Year and Rating 不等式+贪心、数学

My Solution

题意：rating == 1900是区分各个分组的界限，给出给出n个ci 和 di，表示rating上涨了ci分(ci正为涨分负为掉分) 且当场比赛是在di分区大的，不知道起始的rating，只给出了n场连续的比赛涨分情况和所在分组，求出n场比赛之后可能的rating的最大值。

不等式+贪心、数学

很棒的题，

l = -INF, r = INF，l 表示当前rating可能值的最小值，r表示当前rating可能值的最大值。

如果当前分组是div2则r = min(r, 1899),，

如果当前是div2，上一次是div1，则r = min(r, 1899);， l = max(l, 1900);然后l += v,r += v，

如果当前是div1，上一次是div2，则r = min(r, 1899 + prev);，l = max(l, 1900 + prev);，然后l += v,r += v，

其它情况只做普通刷新，且当l > r 时 ans  = -1；

当前所在的分组表示的是上一次比赛结束后，rating所在的分组，

具体见源码 ^_^

复杂度 O(n)

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;
const int INF = 1e8;

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, v, d, l = -INF, r = INF, pred = -1, prev = -1;
    cin >> n;
    int ans = 0;
    for(int i = 0; i < n; i++){
        //cout << l << " " << r << endl; cin >> v >> d;
        if(i == 0){
            if(d == 2){
                r = 1899;
                r += v;
            }
            else if(d == 1){
                l = 1900;
                l += v;
            }
            pred = d;
            prev = v;
            continue;
        }

        if(d == 1){
            if(r < 1900){ ans = -1; //break; } else{ if(pred == 2){ r = min(r, 1899 + prev); r += v; l = max(l, 1900);// l += v; if(l > r){
                        ans = -1;
                    }
                }
                else{
                    if(r != INF) {r += v;}
                    if(l != -INF) {l = max(1900, l); l += v;}
                }
            }
        }
        else if(d == 2){

            if(l >= 1900){

                ans = -1;
                //break;
            }
            else{
                if(pred == 1){

                    r = min(r, 1899);//cout < r){
                        ans = -1;
                    }
                }
                else{
                    if(r != INF) {r = min(r, 1899); r += v; }
                    if(l != -INF) l += v;
                }
            }
        }

        if(l > r){
            ans = -1;
        }

        pred = d;
        prev = v;
    }

    if(ans == -1) cout << "Impossible" << endl;
    else if(r == INF) cout << "Infinity" << endl;
    else cout << r << endl;

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx