糖糖别胡说，我真的不是签到题目(思维)

糖糖别胡说，我真的不是签到题目

https://ac.nowcoder.com/acm/problem/14583

题目描述

从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。

为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.

现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。

输入描述:

第一行只有一个整数T（T<6），表示测试数据的组数。
第二行有两个整数n,m。表示糖糖的个数以及娇姐发功的次数。（1<=n<=50000,1<=bi<=1000000）
第三行到n+2行,每行有两个整数ai,bi,表示第i只糖糖属于那一组以及他的能力值。（0<=ai<=1,1<=bi<=1000000）
第n+3行到第n+m+2行，每行有一个整数ci，表示GTW第i次发功的时间.(1<=ci<=n)

输出描述:

总共T行，第i行表示第i组数据中，糖糖存活的个数。

示例1

输入

1 4 3 0 3 1 2 0 3 1 1 1 3 4

输出

题意

有两组人，第i秒第i个人能杀掉在它前面，不和它一组的，并且能力值比自己小的(注意一样的话是杀不死的)。并且在第ci秒时,前ci个人能力值都会+1，问第n秒存活的人数。

思路

统一到第n秒来计算生死。把应该加上的能力值全部加上，最后进行比较。因为每个人只能杀自己之前的人，而自己也就只能被后面的人杀死，所以从后往前扫描，一旦自己的能力值小于之前出现的不和自己一组的人的能力值，自己就没了，所以在此期间还要维护两个队的能力最大值。注意多组测试，需要清空数据！！

代码

//糖糖别胡说，我真的不是签到题目(思维) 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50010;

int b[N];
pair<int , int> a[N];

int main()
{
	int t;
	scanf("%d" , &t);
	
	while(t--)
	{
		memset(b , 0 , sizeof(b));
		
		int n , m;
		scanf("%d %d" , &n , &m);
		
		int x , y;
		for(int i = 0 ; i < n ; i++)
		{
			scanf("%d %d" , &x , &y);
			a[i] = make_pair(x , y);
		}
		
		for(int i = 0 ; i < m ; i++)
		{
			scanf("%d" , &x);
			b[x - 1]++;
		}
			
		for(int i = n - 1 ; i >= 0 ; i--)
		{
			b[i] += b[i + 1];
			a[i].second += b[i];
		}
		
		int cnt = 0;
		int max0 = -1 , max1 = -1;
		for(int i = n - 1 ; i >= 0 ; i--)
		{
			if(a[i].first == 0)
			{
				max0 = max(max0 , a[i].second);
				if(a[i].second >= max1)
					cnt++;
			}
			else
			{
				max1 = max(max1 , a[i].second);
				if(a[i].second >= max0)
					cnt++;
			}
		}
		
		printf("%d\n" , cnt);
	}
	return 0;
}

牛客算法竞赛入门课第一节习题题解文章被收录于专栏

入门课第一节习题题解