Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


洛谷P1083借教室

题目链接

题目描述

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。

我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份订单,每份订单用三个正整数描述,分别为dj,sj,tj,表示某租借者需要从第sj天到第tj天租借教室(包括第sj天和第tj天),每天需要租借dj个教室。

我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提

供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。


输入格式

第一行包含两个正整数n,m,表示天数和订单的数量。

第二行包含n个正整数,其中第i个数为ri,表示第i天可用于租借的教室数量。

接下来有m行,每行包含三个正整数dj,sj,tj,表示租借的数量,租借开始、结束分别在

第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。


输出格式

如果所有订单均可满足,则输出只有一行,包含一个整数0。
否则(订单无法完全满足)输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人的编号。

解题思路

(先来吐槽一波)这个题真是非常的坑爹,打眼一看就是线段树,可它偏偏卡线段树。各种优化都加上依旧是雷打不动的95分。
如果用线段树做的话,需要修改和查询一起进行,用线段树维护区间最小值。如果修改后的最小值小于零,则不满足订单。放代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1000010;
long long Min[MAXN * 4], n, m, a[MAXN], lazy[MAXN * 4]; //注意要开long long
inline long long min(long long a, long long b) { //自己写min函数跑得快一点
return a < b ? a : b;
}
void build(int l, int r, int rt) { //建树
if (l == r) {
Min[rt] = a[l];
return;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
Min[rt] = min(Min[rt << 1], Min[rt << 1 | 1]);
}
long long update(int L, int R, int C, int l, int r, int rt) { //修改和查询最小值
if (L <= l && r <= R) {
Min[rt] += C;
lazy[rt] += C;
return Min[rt];
}
int m = (l + r) >> 1;
if (lazy[rt]) {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
Min[rt << 1] += lazy[rt];
Min[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
if (L <= m)
update(L, R, C, l, m, rt << 1);
if (R > m)
update(L, R, C, m + 1, r, rt << 1 | 1);
return Min[rt] = min(Min[rt << 1], Min[rt << 1 | 1]);
}

inline int read() { //快读
int ans = 0;
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
while(c >= '0' && c <= '9') {
ans = ans * 10 + (c - '0');
c = getchar();
}
return ans;
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
char c = getchar(); //直接把快读的代码粘过来,减少程序运行时间
while(c < '0' || c > '9')
c = getchar();
while(c >= '0' && c <= '9') {
a[i] *= 10;
a[i] += c - '0';
c = getchar();
}
}
build(1, n, 1);
int d, s, j;
for (int i = 0; i < m; i++) {
d = read(), s = read(), j = read();
if (update(s, j, -d, 1, n, 1) < 0) { //如果修改后的最小值小于0,说明不满足订单
cout << -1 << endl << i + 1 << endl;
return 0;
}
}
cout << 0 << endl;
return 0;
}

当然,dalao们也有用二分来做的,如果前k个教室够用,则前k-1个订单教室是否够用
二分k,判断前k个订单是否满足。
利用前缀和,在总共O(N+M)的时间内求出前K个订单中每天的教室被用了几间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#define N 1000011
int n,m,i,L,R,K,r[N],d[N],s[N],t[N];
long long delta,tag[N];
bool flag;
int main()
{

scanf("%d%d", &n, &m);
for (i=1; i<=n; ++i) scanf("%d", &r[i]);
for (i=1; i<=m; ++i) scanf("%d%d%d", &d[i], &s[i], &t[i]);
L = 0;
R = m+1;
while (R-L > 1)//二分查找
{
K = L+R>>1;
for (i=1; i<=n+1; ++i) tag[i] = 0;
for (i=1; i<=K; ++i)
{
tag[s[i]] -= d[i];
tag[t[i]+1] += d[i];
}
delta = 0;
flag = true;
for (i=1; i<=n; ++i)
{
delta += tag[i];
if (r[i]+delta < 0)
{
flag = false;
break;
}
}
if (flag) L = K; else R = K;
}
if (L == m) printf("0\n");
else printf("-1\n%d\n", R);
return 0;
}

Markdown

最近的文章

铺瓷砖

题目描述 有一面很长很长的墙。 你需要在这面墙上贴上两行瓷砖。 你的手头有两种不同尺寸的瓷砖, 你希望用这两种瓷砖各贴一行。瓷砖的长可以用分数表示,贴在第一行的每块瓷砖长度为A/B,贴在第二行的每块瓷砖长度为C/D。 本问题中你并不需要关心瓷砖的宽度。如上图所示, 两排瓷砖从同一起始位置开始向右排列 …

于  gcd 继续阅读
更早的文章

[codevs]1082线段树3

线段树区间修改求和模板题目链接题目描述 给你N个数,有两种操作:1:给区间[a,b]的所有数增加X2:询问区间[a,b]的数的和。 输入描述 第一行一个正整数n,接下来n行n个整数,再接下来一个正整数Q,每行表示操作的个数,如果第一个数是1,后接3个正整数,表示在区间[a,b]内每个数增加X,如果 …

于  线段树 继续阅读