题目描述
输入格式
输出格式
数据范围
输入样例：
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出样例：
-1
2题目分析
每个订单都是对第s到t这个区间进行操作，所以可以用差分和前缀来实现对这段区间的快速修改。
在1-m个订单中一定会有最后一个能被处理的订单，因此可将1-m分为两个区间，即可被处理的订单，和不可被处理的订单。因此可以使用二分法找到最后一个能被处理的订单。
这里贴一个luogu大佬的详解题解 P1083 【借教室】 - 洛谷专栏
具体实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int w[N];//每天教室的数量
int d[N], s[N], t[N];
long long b[N];//差分数组
二分查找
int l = 0, r = m;//l=0,防止出现一个订单都不符合的情况
while (l < r)
{
int mid = (l + r + 1) / 2;
if (checked(mid))
{
l = mid;
}
else
{
r = mid - 1;
}
}
if (r == m)//如果可以处理所有订单
puts("0");
else
{
printf("-1\n%d", r + 1);//因为二分查找的是最后一个可以满足的订单，因此要+1指向下一个订单
//即第一个不满足条件的订单
}checked代码的具体实现
bool checked(int mid)
{
memset(b, 0, sizeof b);//每次计算前都要清空差分数组
for (int i = 1; i <= mid; i++)//将前mid（包括mid）个订单需要的教室数量进行差分操作，实现前mid个订单每天需要的教室数量
{
b[s[i]] += d[i];
b[t[i]+1] -= d[i];
}
long long S=0;前缀和
for (int i = 1; i <= n;i++)
{
S += b[i];//将差分做一次前缀进行还原
if(S>w[i])//如果某一天的订单不能满足需要就返回false
return false;
}
return true;
}完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int w[N];
int d[N], s[N], t[N];
long long b[N];
bool checked(int mid)
{
memset(b, 0, sizeof b);
for (int i = 1; i <= mid; i++)
{
b[s[i]] += d[i];
b[t[i]+1] -= d[i];
}
long long S=0;
for (int i = 1; i <= n;i++)
{
S += b[i];
if(S>w[i])
return false;
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
}
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &d[i], &s[i], &t[i]);
}
int l = 0, r = m;
while (l < r)
{
int mid = (l + r + 1) / 2;
if (checked(mid))
{
l = mid;
}
else
{
r = mid - 1;
}
}
if (r == m)
puts("0");
else
{
printf("-1\n%d", r + 1);
}
return 0;
}本蒟蒻第一次题解有不足的地方请dalao们谅解