Gym – 101102C C. Bored Judge 线段树+贪心+反向推

Source

2016 ACM Amman Collegiate Programming Contest

UESTC 2017 Winter Training #1

Gym - 101102C

My Solution

题意：给出一系列分数变化情况，x p 表示队伍x获得了p分，求出最终winner在ans事件之后就一直是第一名，求出ans，(如果winner一直是winner，则ans = 1)。

线段树+贪心+反向推

先计算出每个队伍最终的分数，求出winner的最终分数和队伍编号，

然后把每个队伍的分数输入到线段树，用线段数来维护1~n的最大值，存储在team[1]里，

然后反向的遍历事件， Modify(ord[i], -p[i]);如果if(team[1] == maxi){ans = i - 1;}一旦不满足就跳出循环。

对于几个特殊的数据，

第一个事件之前winner 是 team 1st，

故如果

1

2 1

则ans = 1，

如果

1

1 2

则ans = 0，

如果

1

1 -1

则ans = 1，此时winner 是 team 2nd

复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

int pit[maxn], ord[maxn], p[maxn];

int Top[4*maxn], team[4*maxn];
int sz;

void _Modify(int a, int l, int r, int Ind, int d){
    if(l == r && l == a){
        Top[Ind] += d;
        team[Ind] = a;
        return;
   }
    int mid = (l + r) >> 1;
    if(a <= mid) _Modify(a, l, mid,Ind<<1, d);
    else _Modify(a, mid + 1, r, (Ind<<1) + 1, d);
    if(Top[Ind<<1] < Top[(Ind<<1)+1]){
        Top[Ind] = Top[(Ind<<1)+1];
        team[Ind] = team[(Ind<<1)+1];
    }
    else{
        Top[Ind] = Top[Ind << 1];
        team[Ind] = team[Ind << 1]; } } inline void Modify(int a,int d){ _Modify(a,1,sz,1,d);} int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("c.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int T, n, q, ans, maxi, maxp; cin >> T;
    while(T--){
        memset(pit, 0, sizeof pit);
        memset(Top, 0, sizeof Top);
        memset(team, 0, sizeof team);
        cin >> n >> q;
        sz = n;
        for(int i = 1; i <= q; i++){ cin >> ord[i] >> p[i];
            pit[ord[i]] += p[i];
        }
        maxi = 1;
        maxp = -1e9;
        for(int i = 1; i <= n; i++){
           Modify(i, pit[i]);
            if(maxp < pit[i]){
                maxp = pit[i];
                maxi = i;
            }
        }

        ans = q;
        //cout << "m "<<  maxp << endl; for(int i = q; i >= 1; i--){
        //cout << Top[1] << endl;
            Modify(ord[i], -p[i]);
            if(team[1] == maxi){
                ans = i - 1;
            }
            else break;
        }

        cout << ans << endl;

    }
    return 0;
}

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

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx