[NOIP 2012 提高组] 借教室

知识点

二分答案、差分、区间资源

解题思路

检查前k份订单时，对每个需求区间[s,t]在差分s处加d、t+1处减d，扫描累计需求并与可用数量比较。若全部订单可行输出0，否则二分第一个不可行前缀，输出-1及该前缀末订单编号。

正确性说明

所有需求非负，因此前缀一旦不可行，增加订单也不可能恢复可行，满足二分单调性。差分的前缀和恰为每天总需求，故检查判定准确；最小不可行k就是第一位无法满足的申请人。

易错点

区间包含两端；r_i、d_j可为0；累计需求可超过32位，必须64位；不能对订单重新排序。

复杂度

时间O((n+m)log m)，空间O(n+m)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Req{long long d;int s,t;};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<long long>r(n+1),diff(n+2);for(int i=1;i<=n;i++)cin>>r[i];vector<Req>a(m);for(auto&x:a)cin>>x.d>>x.s>>x.t;auto ok=[&](int k){fill(diff.begin(),diff.end(),0);for(int i=0;i<k;i++)diff[a[i].s]+=a[i].d,diff[a[i].t+1]-=a[i].d;long long sum=0;for(int i=1;i<=n;i++){sum+=diff[i];if(sum>r[i])return false;}return true;};if(ok(m)){cout<<0<<'\n';return 0;}int l=1,h=m;while(l<h){int mid=(l+h)/2;if(ok(mid))l=mid+1;else h=mid;}cout<<-1<<'\n'<<l<<'\n';}