[原创]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;
}