作业不做完是不好的,抄作业也是不好的QAQ.
题目描述
高二数学《绿色通道》总共有 n 道题目要抄,编号 1,2,…,n,抄第 i 题要花 ai分钟。
小 Y 决定只用不超过 t
分钟抄这个,因此必然有空着的题。
每道题要么不写,要么抄完,不能写一半。
下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。
这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。
现在,小 Y 想知道他在这 t
分钟内写哪些题,才能够尽量减轻马老师的怒火。
由于小 Y 很聪明,你只要告诉他最长的空题段至少有多长就可以了,不需输出方案。
输入样例
17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
输出样例
3
二分+单调队列
首先假设空题段为m,那么问题就成了能不能在时间t内,完成任意道题,使这些题的最大空题段为m,就简化成了烽火台那道题.空题段很明显是可以通过二分来的,所以这道题就是二分+烽火台.
代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+50;
int n,t;
int a[N],f[N];
struct node {
int t;
int pos;
} q[N];
bool check(int m) {
int head=1,tail=1;
q[1].t=q[1].pos=0;
for(int i=1; i<=n; i++) {
while(q[head].pos<i-m&&head<=tail) head++;
f[i]=q[head].t+a[i];
while(head<=tail&&q[tail].t>=f[i]) tail--;
q[++tail].pos=i;
q[tail].t=f[i];
}
if(f[n]>t) return 0;
return 1;
}
int main() {
scanf("%d%d",&n,&t);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
n++;
a[n]=0;
int l=0,r=n;
int ans=n;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid+1)) {
ans=min(ans,mid);
r=mid-1;
} else l=mid+1;
}
printf("%d",ans);
}