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/P2009

tag:
图论，最短路

思路：
这道题因为读入的时候，会有不同权值的相同的边，要求是如果有重复的就保留最长的那个，这种情况下用邻接链表不是很好做，所以可以用邻接矩阵来存比较方便。然后就是数据范围比较小，k是小于等于100，刚好floyd算法可以过，所以就用floyd来求最短路。

代码：

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int d[110][110];
    memset(d, 0x3f, sizeof d);
    int n, k;

    cin >> n >> k ;
    int c = 0;
    for (int i = 0; i < n; i ++)
    {
        int w;
        cin >> w;
        if (i == n - 1)
        {
            d[i][0] = d[0][i] = w;
        }
        else
        {
            d[i][i + 1] = d[i + 1][i] = w;
        }
    }
    for (int i = 0; i < k; i ++)
    {
        char a, b;
        int w;
        cin >> a >> b >> w;
        if (d[a - 'A'][b - 'A'] == 0x3f3f3f3f) d[a - 'A'][b - 'A'] = d[b - 'A'][a - 'A'] = w;
        else d[a - 'A'][b - 'A'] = d[b - 'A'][a - 'A'] = max(w, d[a - 'A'][b - 'A']);
    }
    for (int q = 0; q < n; q ++)
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++)
                d[i][j] = min(d[i][j], d[i][q] + d[q][j]);

    char s, t;
    cin >> s >> t;
    cout << d[s - 'A'][t - 'A'];
    return 0;

}

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

tag:
kruskal算法, 并查集

思路：
先按照边权排序，然后依次取出每条边，判断两个点是否联通（是否在一个集合）如果不连通就加一条边，然后更新下res = max(res, w) 然后边数++，最后判断边数是否为点个数-1，表示所有点都连上，如果没有则输出-1，否则输出res

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
struct edg {
    int x, y, t;
} Edg[N];
bool cmp(edg &a, edg &b)
{
    return a.t < b.t;
}
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> Edg[i].x >> Edg[i].y >> Edg[i].t;
    }
    sort(Edg + 1, Edg + m + 1, cmp);
    for (int i = 1; i <= n; i ++) p[i] = i;
    int res = 0, cnt = 0;
    for (int i = 1; i <= m; i ++)
    {
        int a = find(Edg[i].x), b = find(Edg[i].y), w = Edg[i].t;
        if (a != b)
        {
            p[a] = b;
            res = max(res, w);
            cnt ++;
        }
    }
    if (cnt < n - 1) cout << -1 << endl;
    else cout << res << 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;
}

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

tag：
二分，贪心

思路：
求可以满足条件的最小值，所以可以想到用二分来做。二分的是复制时间，所以范围是在0到全部的页数。二分的思路是利用这个复制时间来求出一个需要的人数，将这个人数和题目所给的认识做一个比较，因为要满足条件，所以人数需要小于等于题目给的人数。可以知道如果复制时间越大，表示一个人可以抄的书越多，需要的人数越少，所以人数和复制时间是单调递减的关系。利用这个单调递减的关系，可以二分出一个复制时间，使得这个复制时间是当所需人数小于等于所需人数时，复制时间最小。然后就可以通过这个复制时间来求出每一个人所抄的书的起始范围。因为要求是让前面的人尽可能的少抄，所以就需要让后面的人多抄，因此再输出答案的时候用到了贪心的思想，从后往前遍历书，使得每次每个人都尽可能抄多一点的书，通过这种遍历方式实现题目要求的让前面的人尽可能少抄。在二分的时候也有用到这种遍历方式，但是后面写题解的时候觉得或许二分的时候不需要，因为只是求一个人数，没有前后之分。

代码：

#include <iostream>
using namespace std;
int m, k;
const int N = 550;
int a[N];
int x[N], y[N];
bool check(int x)
{
    int now = 1;
    int cnt = 0;
    for (int i = m - 1; i >= 0; i --)
    {
        if (cnt + a[i] > x)
        {
            cnt = 0;
            now ++;
        }
        cnt += a[i];
    }
    return now <= k;
}
int main()
{
    cin >> m >> k;
    int kk = k;
    int l = 0, r = 0;
    for (int i = 0; i < m; i ++)
    {
        cin >> a[i];
        r += a[i];
    }
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    int t = 0;
    y[k] = m; x[1] = 1;
    for (int i = m - 1; i >= 0; i --)
    {
        if (t + a[i] > l)
        {
            t = 0;
            x[k] = i + 2;
            y[--k] = i + 1;
        }
        t += a[i];
    }
    for (int i = 1; i <= kk; i ++)
    {
        cout << x[i] << ' ' << y[i] << '\n';
    }
    return 0;
}