「CF1257D」Yet Another Monster Killing Problem

题意：你有 $m$ 个英雄，你需要打败 $n$ 个怪兽，每个怪兽都有一个力量值 $a _i$ ，每个英雄都有一个力量值 $p _i$ 和耐力值 $s _i$ 。

每天你都可以选择任意一个英雄进入战斗，当英雄进入战场时，他会受到上次未打败的怪兽的挑战(就是如果上次打败了前 $k$ 个怪物，那么这次第 $k+1$ 个怪物会挑战你)。当英雄与怪兽战斗时，有两种情况：

如果怪兽的力量值大于英雄的力量值，英雄会逃跑，今天的战斗结束；
其他情况，怪物被打败。

打败怪物后，如果英雄已经击败了 $s _i$ 个怪兽，那么他必须离开战场，或者直到 $n$ 个怪物都被击败，否则他要继续战斗。

你的目标是打败所有怪物，达到目标的最少天数是多少？(注意怪兽是按顺序依次挑战)。

一道方法多样的题，既可以二分也可以贪心。

我一开始在考场上写二分时写挂了，后来订正时发现可以直接更简单的用贪心算。

我们用一个数组 $e _i$ 代表能连续打败 $i$ 个怪兽的英雄中，最大的力量值(即耐力值大于等于 $i$ 的英雄中力量值最大的)。

然后我们直接拿个指针依次扫描每个怪兽，贪心策略是每天尽量打更多的怪兽，所以我们每次打怪兽时更新今天打的怪兽中力量的最大值 $maxx$ ，设今天打了 $k$ 个怪兽，将 $maxx$ 与 $e[k]$ 比较，判断能否打更多的怪兽。

注意要点千万不要开 memset，今天才知道 memset 的时间复杂度还是 O(n)，只是常数小很多

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n,m;
int a[201010],p[201010];
int s[201010],e[201010];//e[i]代表耐力值大于等于i的英雄中最大的力量值
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		// memset(a,0,sizeof(a));
		// memset(p,0,sizeof(p));
		// memset(s,0,sizeof(s));
		e[0]=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			e[i]=0;
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&p[i],&s[i]);
			e[s[i]]=max(e[s[i]],p[i]);
		}
		for(int i=n-1;i>=0;i--)//注意倒序更新！！
			e[i]=max(e[i],e[i+1]);//能打败i+1个怪兽的也能打败i个怪兽，更新最大值
		int now=1,flag=0,ans=0;//now代表当前打的怪兽是第几个
		while(now<=n)
		{
			ans++;//日期加一天
			int q=now;
			int maxn=0;
			while(q<=n)
			{
				maxn=max(maxn,a[q]);
				if(maxn>e[q-now+1])//如果这个区间内怪兽力量的最大值大于我在这个耐力值内所能达到的最大值，即我打不了它
					break;
				q++;//打下一个怪兽
			}
			if(q==now)//如果一个怪兽都打不了
			{
				flag=1;
				break;
			}
			now=q;//更新打的怪兽的编号
		}
		if(flag)//如果打到一半退出
		{
			printf("-1\n");
			continue;
		}
		printf("%d\n",ans);
	}
	return 0;
}