AcWing 503. 借教室
原题链接
简单
作者:
大佬
,
2024-04-23 19:21:40
,
所有人可见
,
阅读 1
借教室(差分+二分详解版)
二分找答案,差分计算每天的订单数
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int w[N];
int d[N],L[N],R[N];
int n,m;
LL b[N];//操作数组(同时也是差分数组)记录当天需要的所需要的订单数
bool check( int mid )//mid可以理解为我们要操作到的订单(或者为我们通过二分搜素到的订单)
{
memset( b , 0 ,sizeof b);//每次判断都要初始化为0
for( int i = 1; i <= mid; i ++)//从第一个订单处理到我们当前操作的订单
{ //差分思想:因为我们要累加当天的订单但每个订单是从L[i]到R[i]天内进行操作的
//所以我们对b[L[i]]这一天加上b[i],在R[i]的“后一天”减去b[i]及完成了上述操作
b[L[i]] += d[i];
b[R[i] + 1 ] -= d[i];
}
for(int i = 1 ; i <= n ;i ++)
{
b[i] += b[i-1];//进行差分操作
if( b[i] > w[i]) { //如果当天的订单的教室超过当天的教室
//说明不满足要求的订单的前一订单的在 l ~ mid-1 (mid一定不满足)
return false;
}
}
return true;
}
int main()
{
cin >> 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],&L[i],&R[i]);
// 二分找右端点的模板
int l = 0, r = m;// l = 0 是因题而写的,因为有可能第一个订单就不满足(结果会加 1 )
while( l < r)//
{
int mid = (l + r + 1)>>1;
if(check(mid)) l = mid;
else r = mid-1;
}
if (l == m) puts("0");
else printf("-1\n%d\n", l + 1);
return 0;
}