题解 | #【入门班】借教室#

#include<vector>
#include<string.h>
using namespace std;
const int N = 1e6+10;
int room[N];
int d[N];
int s[N];
int t[N];
int diff[N];
int n,m;
bool check(int x)
{    
    for(int i=1;i<=n;i++)
    {
        diff[i]  = room[i]-room[i-1];
    }
    for(int i=1;i<=x;i++)//订单
    {
        diff[s[i]]-=d[i];
        diff[t[i]+1]+=d[i];
    }
    for(int i=1;i<=n;i++)
    {
        diff[i] +=diff[i-1];
        if(diff[i]<0)
            return false;
    }
        
    return true;
}

int main()
{
    vector<int> temp;
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>room[i];
    }
    
    for(int i=1;i<=m;i++)
    {
        cin>>d[i]>>s[i]>>t[i];
    }
    int l = 1,r = m;
    int ans = 0;
    while(l<=r)
    {
        int mid = l - (l-r)/2;
        if(check(mid))
            l = mid+1;
        else
        {
            ans = mid;
            r = mid-1;
        }
    }
    cout<<ans;
}

此题思路较简单，难在复杂度上 利用二分查找来定位到第一个不合理的订单比从前往后遍历找更快 利用差分数组来将需要遍历处理的操作化为两行代码，降低复杂度