借教室——二分、前缀和、差分

题目

思路

• 当某一份订单可以满足的时候，那么他前面的所有订单都可以满足，当某一份订单不能满足的时候，那么他后面的所有订单都不能完成，所以可以使用二分查找来降低时间复杂度
• 每次二分找到一份订单，利用二分与前缀和将当前订单以及之前的所有订单进行预处理，将每一天需要的教室数量和能够分配的数量进行比较，如果大于能够分配的教室数量，返回false，如果都满足返回true
• 先判断m个订单是否都满足，如果有天数不满足，进行二分查找，找到第一个不满足的订单

代码实现

#include <iostream>
#include <cstring>
 
using namespace std;
 
const int N = 1e6 + 10;
typedef long long LL;
 
int n, m;
int ri[N];	// 每天能够分配的教室数量
LL tmp[N];	// 前缀和数组
int di[N], si[N], ti[N];	// 每天借di个，从si天开始，到ti天结束
 
int solve(int u)	// 判断到当前订单是否满足每天都有教室可以借
{
	memset(tmp, 0, sizeof tmp);	// 清空上一次的数据
	for(int i = 1; i<= u; i++)	// 差分，处理当前订单以及之前的所有订单
	{
		tmp[si[i]] += di[i];
		tmp[ti[i] + 1] -= di[i];
	}
	for(int i = 1;i <= n; i++)	// 前缀和，判断是否有哪天教室不够借
	{
		tmp[i] += tmp[i-1];
		if(tmp[i] > ri[i]) return 0;
	}
	return 1;
}
 
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> ri[i];
	for(int i = 1;i <= m; i++) cin >> di[i] >> si[i] >> ti[i];
	if(solve(m)) 	// 先判断所有订单是否都能有教室可借
	{
		cout << 0 << endl;
		return 0;
	}
	int l = 0, r = m + 1;	// 二分查找
	while(l + 1 != r)
	{
		int mid = l + r >> 1;
		if(solve(mid)) l = mid;
		else r = mid;
	}
	cout << -1 << endl;
	cout << r << endl;
	
	return 0;
}