洛谷题单指南-前缀和差分与离散化-P1083 [NOIP2012 提高组] 借教室

原题链接：https://www.luogu.com.cn/problem/P1083

题意解读：已知第i天有r[i]个教室可以供租借，有m个租借教室的订单，第i订单需要在第s[i]~t[i]天区间内租借d[i]个教室，计算是否全部订单都能满足，如果不满足要输出从第几个订单开始不满足。

解题思路：

1、朴素做法

枚举1~m个订单，通过差分减去1~i个订单所需要的教室数量，设a[]为差分数组

a[s[i]] += d[i];
a[t[i] + 1] -= d[i];

再还原前缀和数组s[]，逐项比较r[i]和sum[i]，如果出现r[i] < sum[i]，则找到了不满足需求的订单。

45分代码：

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

const int N = 1000005;
int n, m;
long long r[N], a[N], sum[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> r[i];
    int d, s, t;
    for(int i = 1; i <= m; i++) 
    {
        cin >> d >> s >> t;
        a[s] += d;
        a[t + 1] -= d;

        for(int j = 1; j <= n; j++)
        {
            sum[j] = sum[j - 1] + a[j];
            if(r[j] < sum[j])
            {
                cout << -1 << endl << i;
                return 0;
            }
        }
    }
    
    cout << 0;
    return 0;
}

2、二分

通过枚举订单，来计算1~i个订单所需的教室数量是否符合条件，必须从头遍历所有订单

是否可以二分来求最后一个满足需求的订单编号呢？

单调性分析：订单越少越可能满足需求，订单越多不难以满足需求

设二分到最后一个满足需求的订单编号是x，如果此时1~i号订单所需教室数都能满足，说明订单可以更多一点，x往更大范围找，否则x往更小范围找。

100分代码：

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

const int N = 1000005;
int n, m;
int d[N], s[N], t[N];
long long r[N], a[N], sum[N];

bool check(int x)
{
    memset(a, 0, sizeof(a));
    for(int i = 1; i <= x; i++)
    {
        a[s[i]] += d[i];
        a[t[i] + 1] -= d[i];
    }
    for(int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        if(r[i] < sum[i]) return false;
    }
    return true;
}

int main()
{
    cin >> n >> 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];
    
    int l = 1, r = m, ans = 1; //所有订单都不满足时答案默认是第1个订单
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid))
        {
            ans = mid + 1;
            l = mid + 1;
        }
        else r = mid - 1;
    }
   
    if(ans <= m) cout << -1 << endl << ans;
    else cout << 0;

    return 0;
}