题解
解题思路
这个问题可以通过二分查找和差分数组来解决。我们需要找到第一个无法满足的订单，然后输出其编号。具体步骤如下：
- 二分查找：我们使用二分查找来确定第一个无法满足的订单。对于每个中间值
mid，我们检查前mid个订单是否可以满足。 - 差分数组：为了高效地计算每天的需求，我们使用差分数组。对于每个订单，我们在开始天增加需求，在结束天的下一天减少需求。然后通过前缀和计算每天的总需求。
- 检查函数：在检查函数中，我们遍历所有天数，计算每天的总需求，并与可用教室数量进行比较。如果某天的需求超过可用教室数量，则返回
false，表示前mid个订单不可行。
伪代码：
#include<bits/stdc++.h>
#define int long long
#define M 1000005
using namespace std;
int n, m;
int r[M], d[M], s[M], t[M];
int f[M];
bool check(int mid) {//判断函数
//将f数组初始化为0
for (int i = 1; i <= mid; i++) {
// 在开始天增加需求
// 在结束天的下一天减少需求
//(差分)
}
int c = 0;
for (int i = 1; i <= n; i++) {
c += f[i]; // 计算每天的累计需求
if () { // 如果需求超过可用教室
return false;
}
}
return true;
}
signed main() {
//输入
int left = 1, right = m, ans = 0;
while (left <= right) {
int mid = (left + right) >> 1;
if () { // 检查前mid个订单是否可行
left = mid + 1;
} else {
ans = mid;
right = mid - 1;
}
}
//输出
return 0;
}