[codevs3342][绿色通道]

codevs3342

思路：

既然是要求最小化最长空题段，直接二分答案。然后就是check函数的写法。

先考虑n方转移，假设当前二分的答案是x，用f[i]表示前i个题，第i道题写的最小花费时间。最后再去判断后f数组的后x个值是否小于等于要求时间的。然后返回。

int check(int x) {

	memset(f,0x3f,sizeof(f));

	f[0]=0;

	for(int i=1;i<=n;++i)

		for(int j=i-1;j>=0&&j>=i-x-1;--j)

			f[i]=min(f[i],f[j]+a[i]);

	for(int i=n;i>=n-x;--i)

		if(f[i]<=t) return 1;

	return 0;

}

然后考虑优化这个dp，可以发现每个f[i]都是从前面x个值中的最小值转移过来的，可以用单调队列维护。

int check(int x) {

	Head=1,Tail=1;

	f[0]=0;

	q[1]=0;

	for(int i=1;i<=n;++i) {

		while(q[Head]<i-x-1&&Head<=Tail) Head++;

		f[i]=f[q[Head]]+a[i];

		while(f[q[Tail]]>=f[i]&&Tail>=Head) Tail--;

		q[++Tail]=i;

	}

	return f[q[Head]]<=t;

}

代码

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=50000+100;

int f[N];//f[i]表示前i道题，第i道题做的最小花费时间

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}

int n,t;

int a[N];

int q[N],Head,Tail;

int check(int x) {

	Head=1,Tail=1;

	f[0]=0;

	q[1]=0;

	for(int i=1;i<=n;++i) {

		while(q[Head]<i-x-1&&Head<=Tail) Head++;

		f[i]=f[q[Head]]+a[i];

		while(f[q[Tail]]>=f[i]&&Tail>=Head) Tail--;

		q[++Tail]=i;

	}

	return f[q[Head]]<=t;

}

int main() {

	n=read(),t=read();

	for(int i=1;i<=n;++i) a[i]=read();

	int ans=0,l=0,r=n;

	while(l<=r) {

		int mid=l+r>>1;

		if(check(mid)) r=mid-1,ans=mid;

		else l=mid+1;

	}

	cout<<ans;

	return 0;

}