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 ;
}