Skip to content

11085: 【原1085】绿色通道

题目

题目描述

author: 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1085

Description

《思远高考绿色通道》(Green Passage)是唐山一中常用的练习册之一,其中又以数学绿色通道为最。

2007年某月某日,又一次要交这本作业,而lsz还一点也没有写……

高二数学《绿色通道》总共有n道题目要写(其实是抄),编号1..n,抄每道题所花时间不一样,抄第i题要花a[i]分钟。

由于(当年)lsz还要准备NOIP,显然不能成天写绿色通道。

lsz决定只用不超过t分钟时间抄这个,因此必然有空着的题。

每道题要么不写,要么抄完,不能写一半。

一段连续的空题称为一个空题段,它的长度就是所包含的空白题目数。

这样应付作业自然会引起P老师的愤怒。P老师发怒的程度(简称发怒度)等于最长的空题段长度。

现在,lsz想知道他在这t分钟内写哪些题,才能够尽量降低P老师的发怒。由于lsz很聪明,你只要告诉他发怒度的数值就可以了,不需输出方案。

([email protected]:我们当年的日子不好过啊……)

([email protected]:同做过绿色通道的孩纸伤不起啊……)

Input Format

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

以下一行,为n个整数,依次为a[1], a[2],... a[n],为每道题所需时间。

Output Format

输出仅一行,一个整数w,为最低的发怒度。

说明

样例1解释

分别写第4,6,10,14题,共用时2+3+3+3=11分钟。空题段:1-3(长度为3), 5-5(1), 7-9(3), 11-13(3), 15-17(3)。所以发怒度为3。可以证明,此数据中不存在使得发怒度<=2的作法。

数据规模

40%数据 \( n \leq 2000 \)

60%数据 \( n \leq 60000 \)

100%数据 \( 0 < n \leq 201107,0 < a[i] \leq 3000,0 < t \leq 100000000 \)

题目来源

TSOI2007模拟赛 [2007-09-08], 数据有变化

Sample Input

17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

Sample Output

3

Sample Input

8 3
1 1 1 1 1 1 1 1

Sample Output

2

FineArtz's solution

/* 绿色通道 */
#include <iostream>
#include <cstring>
using namespace std;

int f[201110], a[201110];
pair<int, int> q[201110];
int n, t;

bool check(int lim){
    memset(f, 0, sizeof(f));
    memset(q, 0, sizeof(q));
    int front = 0, rear = 0;
    q[rear++] = make_pair(0, 0);
    for (int i = 1; i <= n; ++i){
        while (front != rear && q[front].first < i - lim - 1)
            ++front;
        f[i] = q[front].second + a[i];
        while (front != rear && f[i] <= q[rear - 1].second)
            --rear;
        q[rear++] = make_pair(i, f[i]);
    }
    for (int i = n - lim; i <= n; ++i)
        if (f[i] <= t)
            return true;
    return false;
}

int main(){
    cin >> n >> t;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    int l = 0, r = n, mid;
    while (l < r){
        mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

yyong119's solution

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 100000007;

int a[201110], f[201110];
int n, t;
struct node {
    int l, r, num;
}tree[1000005];

void buildtree(int index, int l, int r) {

    if (l == r) {
        tree[index].l = l; tree[index].r = r;
        tree[index].num = INF;
    }
    else {
        int mid = (l + r) >> 1;
        buildtree(index << 1, l, mid);
        buildtree(index << 1 | 1, mid + 1, r);
        tree[index].l = l; tree[index].r = r; tree[index].num = INF;
    }
}

void addElement(int index, int pos, int num) {
    if (tree[index].l == pos && tree[index].r == pos) tree[index].num = num;
    else {
        int mid = (tree[index].l + tree[index].r) >> 1;
        if (pos <= mid) addElement(index << 1, pos, num);
        else addElement(index << 1 | 1, pos, num);
        tree[index].num = min(tree[index << 1].num, tree[index << 1 | 1].num);
    }
}

int querymin(int index, int l, int r) {

    if (tree[index].l == l && tree[index].r == r) return tree[index].num;
    int mid = (tree[index].l + tree[index].r) >> 1;
    if (r <= mid) return querymin(index << 1, l, r);
    else if (l > mid) return querymin(index << 1 | 1, l, r);
    else return min(querymin(index << 1, l, mid), querymin(index << 1 | 1, mid + 1, r));
}

bool checkOK(int maxInterval) {

    memset(f, sizeof(f), 0);
    for (int i = 1; i <= maxInterval + 1; ++i) {
        f[i] = a[i];
        addElement(1, i, f[i]);
    }
    for (int i = maxInterval + 2; i <= n; ++i) {
        f[i] = a[i] + querymin(1, i - maxInterval - 1, i - 1);
        addElement(1, i, f[i]);
    }
    for (int i = n - maxInterval; i <= n; ++i)
        if (f[i] <= t) return true;
    return false;
}

int main() {

    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    buildtree(1, 1, n);
    int l = 1, r = n - 2, mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (checkOK(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", r);
    return 0;
}