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