洛谷：P1083：借教室

题目

P1083：借教室

分析

二分的出发点

所有的借教室请求都能满足一定存在一个临界点：第k个请求能满足，但k+1个不能满足。那么显然：k之前的请求都能满足，k+1之后的请求也都不会被满足。这个单调性保证我们可以通过二分法求解。

在实际求解中，我们需要更新不能满足的那个mid量，并修改右边界为mid-1。

    // 二分答案：找第一个无法满足的订单
    int left = 1, right = m;
    int result = -1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (canSatisfy(mid, rooms, orders))
        {
            left = mid + 1; // mid可以满足，加大左边界
        }
        else //不能满足
        {
            result = mid; //保存右边界
            right = mid - 1;
        }
    }

差分数组的应用

题目中明确表示：每份订单用三个正整数描述，分别为\(d_j, s_j, t_j\)，表示某租借者需要从第\(s_j\)天到第\(t_j\)天租借教室（包括这两天），每天需要租借\(d_j\)个教室。这种对一个连续区间同时改变一个固定值的做法，是差分数组的应用。

我们声明Order这个结构来保存订单信息：

struct Order {
    int d, s, t;
};

以及一个diff[n]数组存放1-n个教室每天订量的差分：

int n = rooms.size() - 1;          // rooms[1..n]
vector<long long> diff(n + 2, 0);  // 差分数组

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

然后用差分反求和的方式求出每一天的教室用量并不断求和，如果用量超过了某天可以用的量，直接返回false。

    // 还原实际使用量并检查
    long long used = 0;
    for (int day = 1; day <= n; day++)
    {
        used += diff[day];
        if (used > rooms[day])
        {
            return false;  // 第day天教室不够
        }
    }

答案

思考

二分和差分的联合使用，已经出现了第二次。第一次是在P3017：Brownie Slicing。