[原创]HDU 5596 GTW likes gt 倒推

Tabris

CSDNhdubestcoder

发布于：2016年5月16日

次浏览

[原创]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)
问题描述
从前，有$n$只萌萌的GT，他们分成了两组在一起玩游戏。他们会排列成一排，第$i$只GT会随机得到一个能力值$b_i$。在第$i$秒的时候，第$i$只GT可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的GT。
为了使游戏更加有趣，GT的首领GTW会发功$m$次，第$i$次发功的时间为$c_i$，则在第$c_i $秒结束后，$b_1,b_2,...,b_{c_i}$ 都会增加1。
现在，GTW想知道在第$n$秒之后，会有几只GT存活下来。
输入描述
第一行只有一个整数$T(T\leq 5)$，表示测试数据组数。
第二行有两个整数$n,m$。表示GT的个数和GTW发功的次数。$(1\leq n \leq 50000,1\leq m\leq 50000)$
第三到$n+2$行，每行有两个整数$a_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\leq c[i]\leq n$
输出描述
总共$T$行，第$i$行表示第$i$组数据中，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秒时的值这时候看后面有没有比他大的且是另外一组的
所以
倒序遍历维护两个最大值即可

附本题代码

# 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;
}