P1083 [NOIP 2012 提高组] 借教室——题解

解题思路

“前 $k$ 份订单是否都能满足”具有单调性：若前 $k$ 份失败，加入更多订单也一定失败。二分第一个失败编号。每次检查用差分数组把每个区间订单加到日需求上，再做前缀和并与每天容量比较。若全部订单可满足，直接输出 0。

复杂度分析

每次检查 $O(n+k)$，二分约 $O(\log m)$ 次，总复杂度 $O((n+m)\log m)$，空间 $O(n+m)$。

C++17 参考代码

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

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n,m;cin>>n>>m;vectorr(n+2);for(int i=1;i<=n;i++)cin>>r[i]; vectord(m+1);vectors(m+1),t(m+1);for(int i=1;i<=m;i++)cin>>d[i]>>s[i]>>t[i]; auto ok=[&](int k){vectordiff(n+3,0);for(int i=1;i<=k;i++){diff[s[i]]+=d[i];diff[t[i]+1]-=d[i];}long long use=0;for(int i=1;i<=n;i++){use+=diff[i];if(use>r[i])return false;}return true;}; if(ok(m)){cout<<0<<'\n';return 0;} int lo=1,hi=m,ans=m;while(lo<=hi){int mid=(lo+hi)/2;if(ok(mid))lo=mid+1;else ans=mid,hi=mid-1;} cout<<-1<<'\n'<<ans<<'\n';return 0; }