jzoj1481. 偷懒的西西

Description

高三数学作业总共有n道题目要写(其实是抄)，编号1..n，抄每道题所花时间不一样，抄第i题要花a[i]分钟。由于西西还要准备NOIP，显然不能成天做数学作业。所以西西决定只用不超过t分钟时间抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。一段连续的空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起数学老师的愤怒。数学老师发怒的程度(简称发怒度)等于最长的空题段长度。

现在，西西想知道他在这t分钟内写哪些题，才能够尽量降低数学老师的发怒度。由于西西很聪明，你只要告诉他发怒度的数值就可以了，不需输出方案。(Someone:那么西西怎么不自己写程序？西西：我还在抄别的科目的作业……)

Input

第一行为两个整数n,t，代表共有n道题目，t分钟时间。

以下一行，为n个整数，依次为a[1], a[2],… a[n]，意义如上所述。

Output

仅一行，一个整数w，为最低的发怒度。

Data Constraint

Hint

60%数据 n<=2000

100%数据 0

Solution

签到题。我们可以二分一个最大连续空段，这样就变成了一个最多隔mid个不选的最小方案，f[i]=min{f[j]}+t[i] (i-mid-1<=j

Code

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define erg(i, st) for (int i = ls[st]; i; i = e[i].next)
#define fill(x, t) memset(x, t, sizeof(x))
#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))
#define abs(x) ((x)<(0)?(-(x)):(x))
#define INF 0x3f3f3f3f
#define N 100001
#define E 1001
#define L 1001
int queue[N], f[N], t[N];
inline int read() {
    int x = , v = ; char ch = getchar();
    for(; ch<'0'||ch>'9'; v=(ch=='-')?(-):(v),ch=getchar());
    for(; ch<='9'&&ch>='0'; (x*=)+=ch-'0',ch=getchar());
    return x * v;
}
inline bool check(int n, int m, int mid) {
    fill(f, );
    fill(queue, );
    int head = ;
    int tail = ;
    queue[tail] = ;
    rep(i, , n) {
        while (queue[head] < i - mid -  && head <= tail) {
            head += ;
        }
        f[i] = f[queue[head]] + t[i];
        while (f[queue[tail]] > f[i] && head <= tail) {
            tail -= ;
        }
        queue[++ tail] = i;
    }
    int ans = INF;
    rep(i, n - mid, n) {
        ans = min(ans, f[i]);
    }
    return ans <= m;
}
int main(void) {
    int n = read();
    int m = read();
    rep(i, , n) {
        t[i] = read();
    }
    int l = ;
    int r = n;
    int bobo = ;
    while (l <= r) {
        int mid = (l + r) >> ;
        if (check(n, m, mid)) {
            r = mid - ;
            bobo = mid;
        } else {
            l = mid + ;
        }
    }
    printf("%d\n", bobo);
    return ;
}