题目分类：贪心

题意：

给出一个序列a

每次可以将一个子串(l-r)替换成一个数（al-(r-l)）

要求整个过程中不出现负数且最后整个串可以被替换

要求最少的替换次数

题解：

从头到尾扫，每次能继续则继续否则选出之前的最大的数继续。

使用堆可以十分精妙的实现这道题。

程序：

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int>pq;
int n,a[2200000],T;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		if(n==1)printf("0\n");
		else
		{
			int ans=1,cur=a[1]-1;
			while (!pq.empty())pq.pop();
			for (int i=2;i<=n;i++)
			{
				if(cur!=0)
				{
					cur--;
				}
				else
				{
					ans++;
					if(pq.empty()||pq.top()<2)
					{
						ans=-1;break;
					}
					else
					{
						cur=pq.top()-2;
						pq.pop();
					}
				}
				pq.push(a[i]);
			}printf("%d\n",ans);
		}
	}
	return 0;
}