[原创]HDU 5596 GTW likes gt 倒推

2016-05-16 17:15:07 Tabris_ 阅读数：246

博客爬取于2020-06-14 22:44:28
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51426587

题目链接：

GTW likes gt Accepts: 54 Submissions: 782
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
问题描述
从前，有nn只萌萌的GT，他们分成了两组在一起玩游戏。他们会排列成一排，第ii只GT会随机得到一个能力值bib_i。在第ii秒的时候，第ii只GT可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的GT。
为了使游戏更加有趣，GT的首领GTW会发功mm次，第ii次发功的时间为cic_i，则在第$c_i秒结束后，秒结束后，b_1,b_2,…,b_{c_i}$ 都会增加1。
现在，GTW想知道在第nn秒之后，会有几只GT存活下来。
输入描述
第一行只有一个整数T(T≤5)T(T\leq 5)，表示测试数据组数。
第二行有两个整数n,mn,m。表示GT的个数和GTW发功的次数。(1≤n≤50000,1≤m≤50000)(1\leq n \leq 50000,1\leq m\leq 50000)
第三到n+2n+2行，每行有两个整数ai,bia_i,b_i，表示第ii只GT在哪个组和他的能力值$ (0\leq a[i]\leq 1,1\leq b[i]\leq 10^6)第第n+3行到第行到第n+m+2行，每行有一个整数行，每行有一个整数c_i$ ,表示GTW第ii次发功的时间。1≤c[i]≤n1\leq c[i]\leq n
输出描述
总共TT行，第ii行表示第ii组数据中，GT存活的个数。

输入样例

1
4 3
0 3
1 2
0 3
1 1
1
3
4
输出样例
3

HINT
第1秒后 能力值为4 2 3 1
第2秒后 能力值为4 2 3 1
第3秒后 能力值为5 3 4 1，第2只GT被第3只GT消灭掉了
第4秒后 能力值为6 4 5 2
c[i] 并不是有序的

题目大意 : 详见中闻题面

题解：

本题求解的是最后还剩下多少 , 也就是求有多少被灭了;

在第i秒的时候i能把编号0~i-1的小于他的全灭了
如果每次到第i秒的时候在从前向后遍历一遍的话 必定会超时
所以换个角度
如果编号i被灭了 也就是说后面有比他大且是另外一组的
所以从后面遍历即可

根据c[i]的遍历就能计算出b[i]在i秒时的值 这时候看后面有没有比他大的且是另外一组的
所以
倒序遍历 维护两个最大值即可

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;

int a[50050];
int b[50050];
int c[50050];

int cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));

        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%d %d",&a[i],&b[i]);
        }
        int x;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            c[x]++;
        }

        int sum=n,num=0,jia=0,maxi[2]={-1};

        for(int i=n;i>=1;i--)
        {
            jia+=c[i];

            b[i]+=jia;

            maxi[a[i]]=max(maxi[a[i]],b[i]);

            if(b[i]<maxi[a[i]^1])
                sum--;
        }
        printf("%d\n",sum);
    }
    return 0;
}