（NOIP2012提高组）洛谷P1083题解：二分查找与差分数组完美解决借教室问题

一、问题分析

这道题目描述了一个资源分配问题：学校有n天的教室可用数量，需要处理m个租借订单。每个订单要求在连续几天内每天租借一定数量的教室。我们需要按照订单顺序处理，找出第一个无法满足的订单（如果有的话）。

二、解题思路

1. ‌暴力解法‌：直接按顺序处理每个订单，每天减去租借数量，直到发现某天教室不足。这种方法时间复杂度为O(mn)，对于大数据量会超时。

2. ‌优化解法‌：使用二分查找结合差分数组

• 二分查找第一个无法满足的订单

• 使用差分数组高效计算区间操作

• 时间复杂度优化为O(mlogn)

三、关键算法

1. ‌二分查找‌：通过二分法快速定位第一个无法满足的订单

2. ‌差分数组‌：高效处理区间增减操作，避免每次操作都遍历整个区间

四、完整代码

1. #include <iostream>
   #include <vector>
   using namespace std;
   
   // 检查前mid个订单是否都能满足
   bool check(int mid, vector<int>& rooms, vector<vector<int>>& orders) {
       vector<int> diff(rooms.size() + 2, 0); // 差分数组
       
       // 应用前mid个订单
       for (int i = 0; i < mid; ++i) {
           int d = orders[i][0], s = orders[i][1], t = orders[i][2];
           diff[s] += d;
           diff[t + 1] -= d;
       }
       
       // 计算每天的教室使用量
       int current = 0;
       for (int i = 1; i < rooms.size(); ++i) {
           current += diff[i];
           if (current > rooms[i]) {
               return false; // 某天教室不足
           }
       }
       return true;
   }
   
   int main() {
       int n, m;
       cin >> n >> m;
       
       vector<int> rooms(n + 1); // 每天可用教室数(1-based)
       for (int i = 1; i <= n; ++i) {
           cin >> rooms[i];
       }
       
       vector<vector<int>> orders(m); // 所有订单
       for (int i = 0; i < m; ++i) {
           int d, s, t;
           cin >> d >> s >> t;
           orders[i] = {d, s, t};
       }
       
       // 二分查找第一个无法满足的订单
       int left = 1, right = m, ans = 0;
       while (left <= right) {
           int mid = (left + right) / 2;
           if (check(mid, rooms, orders)) {
               left = mid + 1;
           } else {
               right = mid - 1;
               ans = mid;
           }
       }
       
       if (ans == 0) {
           cout << 0 << endl;
       } else {
           cout << -1 << endl << ans << endl;
       }
       
       return 0;
   }

五、代码解析

1. ‌差分数组应用‌：

• diff[s] += d 表示从第s天开始每天增加d个教室租借

• diff[t+1] -= d 表示从第t+1天开始取消这个租借

2. ‌检查函数‌：

• 应用前mid个订单到差分数组

• 计算每天的教室使用量

• 检查是否有某天教室不足

3. ‌主函数‌：

• 读取输入数据

• 二分查找第一个无法满足的订单

• 输出结果