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

84 阅读 0 评论 56 点赞

我是靠谱客的博主冷静猫咪，最近开发中收集的这篇文章主要介绍Gym - 101102C C. Bored Judge 线段树+贪心+反向推，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Judge Bahosain was bored at ACM AmrahCPC 2016 as the winner of the contest had the first rank from the second hour until the end of the contest.

Bahosain is studying the results of the past contests to improve the problem sets he writes and make sure this won’t happen again.

Bahosain will provide you with the log file of each contest, your task is to find the first moment after which the winner of the contest doesn’t change.

The winner of the contest is the team with the highest points. If there’s more than one team with the same points, then the winner is the team with smallest team ID number.

Input

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains two space-separated integers N and Q (1 ≤ N, Q ≤ 105), the number of teams and the number of events in the log file. Teams are numbered from 1 to N.

Each of the following Q lines represents an event in the form: X P, which means team number X (1 ≤ X ≤ N) got P( - 100 ≤ P ≤ 100, P ≠ 0) points. Note that P can be negative, in this case it represents an unsuccessful hacking attempt.

Log events are given in the chronological order.

Initially, the score of each team is zero.

Output

For each test case, if the winner of the contest never changes during the contest, print 0. Otherwise, print the number of the first event after which the winner of the contest didn’t change. Log events are numbered from 1 to Q in the given order.

   Example 
 

     input 
   
1
5 7
4 5
3 4
2 1
1 10
4 8
3 -5
4 2

     output 
   
5

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，

故如果

2 1

则ans = 1，

如果

1 2

则ans = 0，

如果

1 -1

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

复杂度 O(nlogn)

#include <iostream>
#include <cstdio>
#include <cstring>
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;
}

Thank you!

------from ProLights