绿色通道

题目链接：http://acm.ocrosoft.com/contest.php?cid=1615

题目描述：

高二数学《绿色通道》总共有n道题目要写(其实是抄)，编号1..n，抄每道题所花时间不一样，抄第i题要花a[i]分钟。由于小Y还要准备NOIP，显然不能成天写绿色通道。小Y决定只用不超过t分钟时间抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。一段连续的空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒。马老师发怒的程度(简称发怒度)等于最长的空题段长度。

    现在，小Y想知道他在这t分钟内写哪些题，才能够尽量降低马老师的发怒度。由于小Y很聪明，你只要告诉他发怒度的数值就可以了，不需输出方案。

输入

第一行为两个整数n,t，代表共有n道题目，t分钟时间。

第二行，为n个整数，依次为a[1], a[2],... a[n]，意义如上所述。

输出

输出仅一个整数w，为最低的发怒度。

样例输入：

17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

样例输出：

3

提示

60%数据 n<=2000

100%数据 0<n<=50000，0<a[i]<=3000，0<t<=100000000

思路：

先二分查找1-n的数m，编一个函数去判断空m时,花费的最小时间能不能比t要小，之后继续二分，结束时输出二分的结果就行。

本题的关键就在于编这个函数，我用了deque来写，单调队列去优化，详细见代码注释。

代码：

#include<bits/stdc++.h>
using namespace std;
struct www//此结构体记录dp[i]的位置和值，dp[i]记录的是前i个题，选择做第i题时所需花费的最少时间。
{
	int pos;
	int zhi;
	
} dp[1000005];
int n, t;//总数和时间
int a[1000005];//录入输入的数字
int judge(int m)
{
	memset(dp, 0, sizeof(dp));//每次跑judge（）函数前都要初始化dp数组
	deque<www>kong;//建立dp的双端队列
	for (int i = 1; i <= n; i++)//从做第一题开始到做到第n题
	{
		if (i <= m + 1)//在做到第m+1题前，所花费的最小dp[i]即这题本身的时间
		{
			dp[i].pos = i;
			dp[i].zhi = a[i];
			if (kong.empty())
			{
				kong.push_back(dp[i]);//如果队列为空直接塞入队尾
			}
			else
			{
				while (kong.back().zhi >= dp[i].zhi)//去除冗杂的过程，保证队列是个单调递增队列
				{
					kong.pop_back();
					if (kong.empty())//这句不能少，少了执行到while会报错
					{
						break;
					}
				}
				kong.push_back(dp[i]);//冗杂除完了以后塞入尾部
			}
		}
		else
		{
			if (i - kong.front().pos - 1 > m)//要是加入的dp[i]的位置离队首的位置过远，队首的dp即无效，直接弹出
			{
				kong.pop_front();
				dp[i].pos = i;
				dp[i].zhi = a[i] + kong.front().zhi;//此时的dp[i]和队首有关系了，因为时间的累加性
				while (kong.back().zhi >= dp[i].zhi&&kong.back().pos!=kong.front().pos)
				//去除冗杂，保证单调，“kong.back().pos!=kong.front().pos”这句是防止加入的dp的值和队首的值一样结果把队首给删掉了
				{
					kong.pop_back();
				}
				kong.push_back(dp[i]);
			}
			else//加入的dp[i]的位置和队首的位置正常，直接操作，去除冗杂，保证队列的单调性
			{
				dp[i].pos = i;
				dp[i].zhi = a[i] + kong.front().zhi;
				while (kong.back().zhi >= dp[i].zhi&&kong.back().pos!=kong.front().pos)
				{
					kong.pop_back();
				}
				kong.push_back(dp[i]);
			}
			
		}
	}
	for (int i = n - m; i <= n; i++)//从dp[n-m]到dp[n]，dp[i]包括了挑选不同整串题目的对应时间
	{
		if (dp[i].zhi <= t)//任意一组小于t就行了
		{
			return 1;
		}
	}
	return 0;//没有则空m题不行
}
int main()
{
	scanf("%d %d", &n, &t);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	//一下是二分法找空m题的可行性
	int l = -1;
	int r = n;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (judge(mid))
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
			
	}
	//输出答案
	printf("%d\n", r);
	return 0;
}