题解 | #[NOIP2012]借教室#

不会写线段树

尝试用二分答案+维护差分数组来解决

对于第x号订单，如果无法满足，则往后的都无法满足

AC代码如下：

#include <bits/stdc++.h>
using namespace std;

const int Nmax = 1e6;
const int Mmax = 1e6;
int n,m;
int r[Nmax+5],d[Mmax+5],s[Mmax+5],t[Mmax+5],delta[Nmax+5];
bool juage(int x){
    for(int i = 1;i <= n;i++)    //维护差分数组
        delta[i] = r[i] - r[i - 1];
    
    for(int i = 1;i <= x;i++){
        delta[s[i]] -= d[i];
        delta[t[i]+1] += d[i];
    }
    for(int i = 1;i <= n;i++){
        delta[i] = delta[i]+delta[i-1];
        if(delta[i] < 0) return true;
    }
    return false;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>m;
    int L = 1,R = m;
    for(int i = 1;i <= n;i++)
        cin>>r[i];
    for(int i = 1;i <= m;i++)
        cin>>d[i]>>s[i]>>t[i]; 
    
    //二分答案+检验
    while(L <= R){
        int mid = L + (R - L)/2;
        if(juage(mid)) R = mid - 1;
        else L = mid + 1;
    }
    if(R+1 > m) cout<<0;
    else cout<<-1<<'\n'<<R+1;
    return 0;
}