3342 绿色通道
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
《思远高考绿色通道》(Green Passage, GP)是唐山一中常用的练习册之一，其题量之大深受lsz等许多oiers的痛恨，其中又以数学绿色通道为最。2007年某月某日，soon-if (数学课代表)，又一次宣布收这本作业，而lsz还一点也没有写……
高二数学《绿色通道》总共有n道题目要写(其实是抄)，编号1..n，抄每道题所花时间不一样，抄第i题要花a[i]分钟。由于lsz还要准备NOIP，显然不能成天写绿色通道。lsz决定只用不超过t分钟时间抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。一段连续的空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒。马老师发怒的程度(简称发怒度)等于最长的空题段长度。
现在，lsz想知道他在这t分钟内写哪些题，才能够尽量降低马老师的发怒度。由于lsz很聪明，你只要告诉他发怒度的数值就可以了，不需输出方案。(快乐融化：那么lsz怎么不自己写程序？lsz：我还在抄别的科目的作业……)
输入描述 Input Description
第一行为两个整数n,t，代表共有n道题目，t分钟时间。
以下一行，为n个整数，依次为a[1], a[2],... a[n]，意义如上所述。
输出描述 Output Description
仅一行，一个整数w，为最低的发怒度。
样例输入 Sample Input
17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
60%数据 n<=2000
100%数据 0<n<=50000，0<a[i]<=3000，0<t<=100000000
暴力74分
测试点#gp1.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp10.in 结果:AC 内存使用量: 492kB 时间使用量: 4ms
测试点#gp11.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp12.in 结果:AC 内存使用量: 492kB 时间使用量: 1ms
测试点#gp13.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp14.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp15.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp16.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp17.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp18.in 结果:AC 内存使用量: 492kB 时间使用量: 4ms
测试点#gp19.in 结果:AC 内存使用量: 360kB 时间使用量: 1ms
测试点#gp2.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp20.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp21.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp22.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp23.in 结果:AC 内存使用量: 492kB 时间使用量: 4ms
测试点#gp24.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp25.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp26.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp27.in 结果:AC 内存使用量: 488kB 时间使用量: 1ms
测试点#gp28.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp29.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp3.in 结果:AC 内存使用量: 492kB 时间使用量: 3ms
测试点#gp30.in 结果:AC 内存使用量: 488kB 时间使用量: 4ms
测试点#gp31.in 结果:AC 内存使用量: 488kB 时间使用量: 27ms
测试点#gp32.in 结果:AC 内存使用量: 492kB 时间使用量: 763ms
测试点#gp33.in 结果:TLE 内存使用量: 616kB 时间使用量: 1000ms
测试点#gp34.in 结果:TLE 内存使用量: 620kB 时间使用量: 1000ms
测试点#gp35.in 结果:TLE 内存使用量: 620kB 时间使用量: 1000ms
测试点#gp36.in 结果:TLE 内存使用量: 616kB 时间使用量: 1000ms
测试点#gp37.in 结果:AC 内存使用量: 364kB 时间使用量: 503ms
测试点#gp38.in 结果:TLE 内存使用量: 616kB 时间使用量: 1000ms
测试点#gp39.in 结果:AC 内存使用量: 492kB 时间使用量: 19ms
测试点#gp4.in 结果:AC 内存使用量: 492kB 时间使用量: 4ms
测试点#gp40.in 结果:TLE 内存使用量: 620kB 时间使用量: 1000ms
测试点#gp41.in 结果:TLE 内存使用量: 620kB 时间使用量: 1000ms
测试点#gp42.in 结果:AC 内存使用量: 492kB 时间使用量: 382ms
测试点#gp43.in 结果:TLE 内存使用量: 616kB 时间使用量: 1000ms
测试点#gp44.in 结果:TLE 内存使用量: 616kB 时间使用量: 1000ms
测试点#gp45.in 结果:TLE 内存使用量: 616kB 时间使用量: 1000ms
测试点#gp46.in 结果:AC 内存使用量: 492kB 时间使用量: 322ms
测试点#gp47.in 结果:TLE 内存使用量: 620kB 时间使用量: 1000ms
测试点#gp48.in 结果:TLE 内存使用量: 620kB 时间使用量: 1000ms
测试点#gp49.in 结果:TLE 内存使用量: 616kB 时间使用量: 1000ms
测试点#gp5.in 结果:AC 内存使用量: 488kB 时间使用量: 1ms
测试点#gp50.in 结果:AC 内存使用量: 492kB 时间使用量: 826ms
测试点#gp6.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
测试点#gp7.in 结果:AC 内存使用量: 492kB 时间使用量: 6ms
测试点#gp8.in 结果:AC 内存使用量: 492kB 时间使用量: 0ms
测试点#gp9.in 结果:AC 内存使用量: 488kB 时间使用量: 0ms
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 50001 using namespace std;
int n,t,ans;
int f[maxn],a[maxn]; bool check(int mid)
{
memset(f,/,sizeof f);
f[]=;
for(int i=;i<=n;i++)
for(int j=max(i-mid-,);j<i;j++)
f[i]=min(f[i],f[j]+a[i]);
ans=0x3f3f3f3f;
for(int i=n-mid-;i<=n;i++)
ans=min(ans,f[i]);
return ans<=t; } int main()
{
scanf("%d%d",&n,&t);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int l=,r=n;
while(l<r)
{
int mid=(l+r)>>;
if(check(mid))
r=mid;
else l=mid+;
}
printf("%d\n",l);
return ;
}
心若向阳，无言悲伤
AC
/*用f[i]表示在做第i道题的情况下，前i道题在合法状况下（即空题段长度不超过mid）
可能的所有方案中的最小时间
那么转移方程为 f[i]=min(f[j])+a[i];
其中j的范围是i-mid-1<=j<=i-1
这是因为我们保证a[i]入选，且由于最大空时段为mid
枚举j应当从i之前不做mid个的前面那一道题开始
由于每个f[j]内的状态必然是合法的最小值，
也就是最长空时段不超过mid的最小值，而j又一定被选中（做这道题），最终方案也一定是合法的。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 50010 using namespace std;
int n,m,ans,t;
int a[maxn],f[maxn],q[maxn]; bool check(int mid)
{
memset(f,/,sizeof f);
f[]=;
int l=,r=;
q[r++]=;
for(int i=;i<=n;i++)
{
while(l<=r&&q[l]<i-mid-) l++;//删除队列头部所有位置小于查询起始位置的数字
f[i]=f[q[l]]+a[i];//查询修改后的头元素（最小元素）
while(l<=r&&f[q[r]]>=f[i]) r--;//删除队列尾部所有耗时比当前元素大的元素
q[++r]=i;
}
/*
等价于f[i]=最小的f[j]+a[i];
i跟j之间空着一段mid 所以j就是i-mid-1
*/
int ans=0x3f3f3f3f;
for(int i=n-mid-;i<=n;i++)
ans=min(ans,f[i]);
return ans<=t;
} int main()
{
scanf("%d%d",&n,&t);
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
int l=,r=n;
while(l<r)
{
int mid=(l+r)>>;
if(check(mid))
r=mid;
else l=mid+;
}
printf("%d\n",l);
return ;
}