刷题: 借教室
题目描述
学校每天有一定数量的教室可供租借。现在你获得了接下去$n$天的空闲教室信息，第$i$天有$r_i$ 个教室可供租借。系统一共有$m$份租借订单，已经按照申请时间从早到晚排序。第$j$份订单由一个三元组$\{d_j,s_j,t_j\}$描述，表示需要在第$s_j$天到第$t_j$天期间每天租借$d_j$个教室 (包括第$s_j$ 天和第$t_j$天)。租借者对具体教室没有要求。
按照先到先得的原则处理订单。如果某个订单在其租借期间有任何一天剩余教室数量不足，则需
要通知该申请人修改订单，并停止处理后续订单。
请判断是否存在无法满足的订单。如果存在，输出需要修改订单的申请人编号。
输入描述
第一行输入两个整数$n,m\left(1\leq n,m\leq10^6\right)$代表天数和订单的数量。
第二行输入$n$个整数$r_1,r_2,\cdots,r_n\left(0\leq r_i\leq10^9\right)$代表每一天可用于租借的教室数
量。
此后$m$行，第$i$行输入三个整数$d_i,s_i,t_i\left(0\leq d_i\leq10^9;1\leq s_i\leq t_i\leq n\right)$代表租借
的教室数量、租借开始时间、租借结束时间。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。
输出描述
如果订单无法完全满足，在一行上输出一个整数代表需要修改的订单申请人编号；否则，直接输出 0 。
申请人编号即输入顺序，从 1 开始计数。
输入示例
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4输出示例
2说明
第一份订单满足后，这四天剩余的教室数为$\{0,3,2,3\}$ 。
第二份订单要求第二天到第四天每天提供3个教室，而第三天剩余的教室数为2 ,因此
无法满足。分配停止，通知第二个申请人修改订单。
解题思路
要把某个区间的教室全部借走, 想了下, 应该要用到差分数组, 不过好像从订单 1 枚举到订单 m, 好像会超时.
想了下, 这个系列不是二分答案吗, 那就用二分来枚举答案就行
整个题不难, 但是是两个经典算法的融合版本.
ac 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int r[N], d[N], s[N], t[N];
int b[N], bb[N];
bool check(int x) // 前 x 个订单是否合法,一个一个枚举也会超时,需要二分
{
memcpy(bb, b, sizeof b);
for (int i = 1; i <= x; i++)
{
int ss = s[i], tt = t[i], dd = d[i];
bb[ss] -= dd;
bb[tt + 1] += dd; // 差分数组
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += bb[i];
if (ans < 0)
return true; // 这个订单需要 修正
}
return false; // 不需要修正
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> r[i];
b[i] = r[i] - r[i - 1];
}
for (int i = 1; i <= m; i++)
cin >> d[i] >> s[i] >> t[i];
int l = 0, r = m, ans = 0;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid)) // 需要修正就再往前看看
ans = mid, r = mid - 1;
else // 不需要修正 就继续往后看
l = mid + 1;
}
cout << ans << endl;
}
