url: https://www.luogu.com.cn/problem/P4552

tag:
差分

思路：
说是一道差分的题，但觉得更像是脑筋急转弯的那种感觉。为了求出最少的操作次数，可以依次求a(i) - a(i-1)，表示相邻两个数的差，然后将正的差和负的差分别求和，之后取这两个和的最大值就是最少的操作次数，因为对于差分来说，如果要对原数组的某一个区间加上1就是让这个区间的第一个数加1最后一个数的后一个数减一，所以加1和减1会有重叠，因此重叠的部分只需要算一次就好，然后剩下的不重叠的再单独算，所以最少的操作次数就是max(q, p)，而对于多少种情况来讲，其实看的是a(1)，因为最后数都一样的话，那么对于差分数组（代码没有）来说，第一个数会影响全部的数。所以只要把有可能会对第一个数产生影响的次数加在一块再加上本身一种情况就是最多可能的结果数。而这种会影响的次数其实就是不重叠的次数，也即max(p, q) - min(p, q)，（min(p, q)用来表示重叠的次数）。

代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
long long a[N], b[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    long long p = 0, q = 0;
    for (int i = 2; i <= n; i ++)
    {

        long long tmp = a[i] - a[i - 1];
        if (tmp > 0) p += tmp;
        else q -= tmp;
    }
    cout << max(q, p) << '\n' << max(q, p) - min(q, p) + 1 << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1083

tag:
差分，前缀和，二分

思路：因为要求第一个不满足要求的订单，所以可以想到用二分。二分查找的是不满足要求的情况。通过订单的编号来查找，因为题目中写道有一个不满足要求的订单，后面就会停止分配，这可以抽象成假如有一个订单不满足，后面的订单一定也不满足，而前面的订单或许会满足，这就给二分提供了二段性。求是否满足条件这一块用到了差分，因为有一个区间加一个数这个标志，我们可以先开一个数组表示假如可以借出教室时每天需要有的教室数。通过前缀和求出这个教室数，然后和每天读入的可以借出的教室数比较，如果大于这个可以借出的教室数则表示不满足要求，返回true（因为求的就是不满足要求的订单的最小值，也就是第一个不满足要求的订单。）最后遍历完都符合则返回false。细节方面，因为求前缀和，用到了加法，然后题目的数据范围比较大，所以为了防止超过int的范围，可以让前缀和数组，也就是差分数组的类型为long long.同时因为是开了long long,所以在求前缀和的过程中反复使用的b数组的初始化就需要变成sizeof(long long) * (n + 1) ,（这里下标从1开始，一共n天所有有n + 1个数）。在输出结果的时候还有一个细节，就是题目说会有完全符合的情况，输出0，这里可以在二分的时候多一个标志，假如一直没有出现check(mid) 返回true的情况就说明完全符合，就输出0，反之，假如有一次check(mid)是true的情况就让这个标志为true，之后输出就输出二分结果即可。

代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int n, m;
long long a[N], b[N];
struct lend {
    int d, s, t;
} Lend[N];
bool check(int x)
{
    memset(b, 0, sizeof(long long) * (n + 1));
    for (int i = 1; i <= x; i ++)
    {
        b[Lend[i].s] += Lend[i].d;
        b[Lend[i].t + 1] -= Lend[i].d;
    }
    for (int i = 1; i <= n; i ++)
    {
        b[i] += b[i - 1];
        if (b[i] > a[i]) return true;
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= m; i ++)
    {
        cin >> Lend[i].d >> Lend[i].s >> Lend[i].t;
    }
    int l = 1, r = m;
    bool res = false;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            res = true;
            r = mid;
        }
        else l = mid + 1;
    }
    if (!res) cout << 0 << endl;
    else cout << -1 << '\n' << l << endl;
    return 0;
}