洛谷P1083《借教室》

一月 24, 2019 5775

前缀和 + 二分答案

题目描述

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

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

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

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 d_j 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

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

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

输入输出格式
输入格式：
第一行包含两个正整数 n,m ，表示天数和订单的数量。

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

接下来有 m 行，每行包含三个正整数 d_j,s_j,t_j ，表示租借的数量，租借开始、结束分别在第几天。

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

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 0 。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 −1 ，第二行输出需要修改订单的申请人编号。

输入输出样例

输入样例

1
2
3
4
5
4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

输出样例

1
2
-1 
2

说明

【输入输出样例说明】

第 1 份订单满足后， 4 天剩余的教室数分别为 0,3,2,3 。第 2 份订单要求第 2 天到第 4 天每天提供 3 个教室，而第 3 天剩余的教室数为 2 ，因此无法满足。分配停止，通知第 2 个申请人修改订单。

【数据范围】

对于10%的数据，有 1≤ n,m≤ 10 ；

对于30%的数据，有 1≤ n,m≤1000 ；

对于 70%的数据，有 1 ≤ n,m ≤ 10^5 ；

对于 100%的数据，有 1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n​ 。

NOIP 2012 提高组 第二天 第二题

解题思路

考虑二分答案

首先我们知道，对于一个订单 i ，如果它能被批准，那么 [1,i] 都能被批准；如果它不能被批准，那么 [i,m] 都不能被批准（单调性）

那么我们二分订单的编号 \text{mid} ，每次判一下 [1,\text{mid}] 是否全都能满足，最后如果右边界不是 m 了，说明有订单不能满足，输出右边界即可

如何判断是否能满足？
首先我们要 O(1) 实现区间修改（？？？）
用前缀和就可以实现！

想想下面的过程 \downarrow 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
原数列:   0  0  0  0  0  0
       [ 1  2  3  4  5  6 ]
前缀和：  0  0  0  0  0  0
       [ 1  2  3  4  5  6 ]
       
我们让[1,3]都增加2
于是我们选择让[1]增加2，让[4]（即[3+1]）减去2
那么上面的数列就变成了：

原数列:   2  0  0 -2  0  0
       [ 1  2  3  4  5  6 ]
前缀和：  2  2  2  0  0  0
       [ 1  2  3  4  5  6 ]

这个时候前缀和数组就实现了区间加！

那么依照上面的思想，我们就能写出Check(int mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Order {
    int amount, l, r;
    
    Order() { amount = l = r = 0; }
} order[MAXM];

int a[MAXN], sum[MAXN];

bool Check(int __i) {
    memset(sum, 0, sizeof sum);
    for (int i = 1; i <= __i; ++i) {
        // 像上面一样处理前缀和
        sum[order[i].l] += order[i].amount;
        sum[order[i].r] -= order[i].amount;
    }
    for (int i = 1; i <= n; ++i) {
        // 将前缀和处理一遍
        // 判一下是否有超过当天可用教室的值
        sum[i] += sum[i - 1];
        if (sum[i] > a[i]) return false; // 不合法
    }
    return true; // 合法
}

代码实现

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXNM = 1000000 + 10;
    
    struct Order {
        int num;
        int l, r;
        
        Order() { num = l = r = 0; }
    } order[MAXNM];
    
    int n, m, seq[MAXNM];
    int sum[MAXNM];
    
    bool Check(int M) {
        memset(sum, 0, sizeof sum);
        for (int i = 1; i <= M; ++i) {
            sum[order[i].l] += order[i].num;
            sum[order[i].r + 1] -= order[i].num;
        }
        for (int i = 1; i <= n; ++i) {
            sum[i] += sum[i - 1];
            if (sum[i] > seq[i]) return false;
        }
        return true;
    }
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using namespace FastIO;
    n = getint();
    m = getint();
    For (i, 1, n) seq[i] = getint();
    For (i, 1, m) {
        order[i].num = getint();
        order[i].l = getint();
        order[i].r = getint();
    }
    int L = 1, R = m;
    while (L < R) {
        int mid = (L + R) >> 1;
        if (Check(mid)) L = mid + 1;
        else R = mid;
    }
    if (R != m) {
        printf("-1\n%d\n", R);
    } else puts("0");
    return 0;
}