【一本通OJ 1603：绿色通道】题解

题目链接

题目

高二数学《绿色通道》总共有 \(n\) 道题目要抄，编号 \(1\ldots n\)，抄第 \(i\) 题要花 \(a_i\) 分钟。小 Y 决定只用不超过 \(t\) 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。

现在，小 Y 想知道他在这 \(t\) 分钟内写哪些题，才能够尽量减轻马老师的怒火。由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

思路

由于最长长度和最短时间都不确定。我们可以假设其中一项确定来思考。

考虑二分答案，二分最长空题段。

假设二分当前最长空题段为 \(k\)，我们就可以尝试dp处理。

设 \(dp_i\) 表示第 \(i\) 题做，且前 \(i\) 题的最长空题段小于等于 \(k\) 时的最短时间，我们可以枚举上一条做了的题，即：

答案我们可以在 \([n-k-1, n]\) 里枚举最后一道题的位置，时间复杂度 \(O(n^2\log n)\)。

显然，\(\min_{\max(j=i-k-1, 0)}^{i-1}dp_j\) 可以用单调队列优化，时间复杂度 \(O(n\log n)\)。

总结

这是一道二分+单调dp的模板。

题目问最长能多长，可以考虑二分，成为切入点。

当最长长度确定，dp也很容易可以写出。

超时后也容易发现，式子中可以用单调队列优化，代码不难打。

Code

// Problem: 1603：绿色通道
// Contest: SSOIER
// URL: http://ybt.ssoier.cn:8088/problem_show.php?pid=1603
// Memory Limit: 524 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define mo
#define N 500010
//#define M
int n, m, i, j, k; 
int l, r, mid, ans; 
int dp[N], a[N], t; 
pairp; 
deque >q; 

int check(int k)
{
	q.clear(); 
	p.first=0; p.second=0; 
	q.push_back(p); 
	for(i=1; i<=n; ++i)
	{	 
		dp[i]=q.front().first+a[i]; 
		while(!q.empty() && i-q.front().second>k) q.pop_front();
		while(!q.empty() && dp[i]<=q.back().first) q.pop_back(); 
		
		p.first=dp[i]; p.second=i; 
		q.push_back(p); 
	}
	ans=0x7fffffffffffffff; 
	for(i=n-k-1; i<=n; ++i) ans=min(ans, dp[i]); 
	return ans<=t; 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); t=read(); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	l=1, r=n; 
	while(l>1; 
		if(check(mid)) r=mid; 
		else l=mid+1; 
	}
	printf("%lld", l); 
	return 0;
}