题解 | #【入门班】借教室#

题目链接

题目描述

有 $n$ 天和 $m$ 份订单。第 $i$ 天有 $r_i$ 个空闲教室。第 $j$ 份订单需要从第 $s_j$ 天到第 $t_j$ 天，每天租借 $d_j$ 个教室。订单按顺序处理，如果一份订单在申请的任何一天无法得到满足（即当天剩余教室不够），则该订单失败，并停止处理后续所有订单。求第一个失败的订单编号。如果所有订单都能满足，则输出 $0$ 。

解题思路

一个直接的想法是按顺序模拟处理每份订单，对于每份订单，都更新对应区间的教室数量。这种方法的时间复杂度为 $O(n \cdot m)$ ，对于 $n, m$ 数量级达到 $10^6$ 的数据会超时。

注意到问题要求的是第一个无法满足的订单，这具有一种临界点的特性，并且满足单调性：如果前 $k$ 份订单可以被满足，那么任何少于 $k$ 份的订单也都能被满足；反之，如果前 $k$ 份订单无法被满足，那么任何多于 $k$ 份的订单也一定无法满足。

这种单调性是使用二分答案的典型特征。我们可以二分订单的数量，将问题从“求解第一个失败的订单编号”转化为一个判定性问题：“判断前 mid 份订单是否能够被满足？”

为了高效地实现这个 check(mid) 函数，我们需要快速计算出前 mid 份订单对每一天教室的需求总量。一份订单 $(d, s, t)$ 相当于对一个区间 $[s, t]$ 上的需求量都加上 $d$ 。对 mid 份订单进行这样的操作，可以使用差分数组来优化。

check(mid) 函数实现：

创建一个大小为 $n+2$ 的差分数组 diff，并初始化为 $0$ 。
遍历前 mid 份订单，对于每份订单 $(d_j, s_j, t_j)$ ，执行 diff[s_j] += d_j 和 diff[t_j + 1] -= d_j。
对差分数组 diff 求前缀和，以还原每一天的总需求量。设 needed_rooms 为当天总需求。
在计算前缀和的同时，逐天进行判断。对于第 $i$ 天（从 $1$ 到 $n$ ），计算出当天的总需求 needed_rooms，如果 needed_rooms > r_i，说明教室不足，前 mid 份订单无法满足，返回 false。
如果遍历完所有天都没有出现教室不足的情况，说明前 mid 份订单可以满足，返回 true。

check(mid) 函数的时间复杂度为 $O(n + mid)$ 。

二分查找过程：

设定二分区间 [left, right] 为 [1, m]。
取 mid，执行 check(mid)。
若 check(mid) 为 true，说明前 mid 份订单都能满足，失败的订单（如果有）在 mid 之后，因此 left = mid + 1。
若 check(mid) 为 false，说明在处理前 mid 份订单时已经出现了失败情况，这个 mid 是一个潜在的答案，我们尝试在更小的范围里寻找第一个失败的，因此 ans = mid, right = mid - 1。
二分结束后，ans 即为第一个失败的订单编号。若从未更新过 ans（即所有订单都能满足），则输出 $0$ 。

总的时间复杂度为 $O((n+m) \log m)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <tuple>

using namespace std;

bool check(int k, int n, int m, const vector<int>& r, const vector<tuple<int, int, int>>& orders) {
    if (k == 0) return true;
    vector<long long> diff(n + 2, 0);

    for (int i = 0; i < k; ++i) {
        int d, s, t;
        tie(d, s, t) = orders[i];
        diff[s] += d;
        diff[t + 1] -= d;
    }

    long long needed_rooms = 0;
    for (int i = 1; i <= n; ++i) {
        needed_rooms += diff[i];
        if (needed_rooms > r[i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;

    vector<int> r(n);
    for (int i = 0; i < n; ++i) {
        cin >> r[i];
    }

    vector<tuple<int, int, int>> orders(m);
    for (int i = 0; i < m; ++i) {
        cin >> get<0>(orders[i]) >> get<1>(orders[i]) >> get<2>(orders[i]);
    }

    int left = 1, right = m;
    int ans = 0;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid, n, m, r, orders)) {
            left = mid + 1;
        } else {
            ans = mid;
            right = mid - 1;
        }
    }

    if (ans == 0) {
        cout << 0 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] r;
    static int[][] orders;

    private static boolean check(int k) {
        if (k == 0) return true;
        long[] diff = new long[n + 2];

        for (int i = 0; i < k; i++) {
            int d = orders[i][0];
            int s = orders[i][1];
            int t = orders[i][2];
            diff[s] += d;
            diff[t + 1] -= d;
        }

        long neededRooms = 0;
        for (int i = 1; i <= n; i++) {
            neededRooms += diff[i];
            if (neededRooms > r[i - 1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        r = new int[n];
        for (int i = 0; i < n; i++) {
            r[i] = sc.nextInt();
        }

        orders = new int[m][3];
        for (int i = 0; i < m; i++) {
            orders[i][0] = sc.nextInt(); // d
            orders[i][1] = sc.nextInt(); // s
            orders[i][2] = sc.nextInt(); // t
        }

        int left = 1, right = m;
        int ans = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid)) {
                left = mid + 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }
        
        System.out.println(ans);
    }
}

import sys

def check(k, n, r, orders):
    if k == 0:
        return True
    
    diff = [0] * (n + 2)
    for i in range(k):
        d, s, t = orders[i]
        diff[s] += d
        if t + 1 <= n:
            diff[t + 1] -= d
            
    needed_rooms = 0
    for i in range(1, n + 1):
        needed_rooms += diff[i]
        if needed_rooms > r[i - 1]:
            return False
    return True

def main():
    n, m = map(int, sys.stdin.readline().split())
    r = list(map(int, sys.stdin.readline().split()))
    orders = []
    for _ in range(m):
        orders.append(list(map(int, sys.stdin.readline().split())))

    left, right = 1, m
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        if check(mid, n, r, orders):
            left = mid + 1
        else:
            ans = mid
            right = mid - 1
            
    print(ans)

if __name__ == "__main__":
    main()

算法及复杂度

算法：二分答案 + 差分数组。
时间复杂度： $O((n+m) \log m)$ 。二分查找需要 $O(\log m)$ 次，每次 check 函数内部需要遍历前 mid (最多 $m$ ) 个订单和 $n$ 天，复杂度为 $O(n+m)$ 。
空间复杂度： $O(n+m)$ ，用于存储教室信息、订单信息和差分数组。