7488-绿色通道

题目要求抄写题目时间满足不超过$t$的前提下，最长的空题段的长度最少是多少？
最长空题段最少是多少？ 显然可以考虑用二分答案来查找空题段的长度，关键如何验证？
回想一下2697-修建草坪，选取若干个淘汰的数，使剩下的区间长度不超过$k$，求这些区间的总和。
那么此题，根据二分答案找的空题段长度，选取若干个数，如果存在总和不超过$t$的方案（寻找和最小的方案，即最小的和如果符合，说明存在一种方案可以划分），则验证通过，反之没通过。
进一步分析

bool check(int x)
{
	memset(q,0,sizeof q);
	memset(pos,0,sizeof pos);
	memset(dp,0,sizeof dp);
	int head = 0, tail = 0;
	for(int i = 1; i <= n; i++){
		dp[i] = q[head] + a[i];
		while(head <= tail && i - pos[head] > x) head++;
		while(head <= tail && q[tail] >= dp[i]) tail--;
		q[++tail] = dp[i];
		pos[tail] = i;
	}
	int k = 2e9;
	for(int i = n - x; i <= n; i++) k = min(k,dp[i]);
	if(k > t) return 0;
	return 1;
}

此处$int$实为$longlong$

#define int long long