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;
}

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

tag:
二分，模拟

思路：
思路比较简单，根据题目可以知道当n越小时切出来的题目数量越多，根据这个来二分。分别二分出一个最小值和一个最大值。这道题是细节比较 恶心（bushi 多，需要注意的点比较多。第一个是二分的范围，题目只有一个xi的范围是1e-9到1e9，经测试，r开到1e9范围比较小，看了题解之后发现需要开到1e18.然后这里就有一个问题，因为超过了1e9所以变量不能放到main()函数中，只能放到外面当全局变量。然后如果是mid要用long long类型，记得check函数的函数签名中变量的类型也要是long long。第二个细节是l要从1开始，不能从0开始。第三个细节是，题目没有保证说如果其中一个答案比如最小值存在，另外一个答案就会存在，所以对于最小值和最大值都要进行验证。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
long long n, k, l ,r;
long long p[N];

long long check (long long x)
{
    long long sum = 0, cnt = 0;
    for (int i = 0; i < n; i ++)
    {
        if (p[i] > 0) sum += p[i];
        else sum = max((long long)0, sum + p[i]);
        if (sum >= x)
        {
            sum = 0;
            cnt ++;
        }
    }
    return cnt;
}
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < n; i ++) scanf("%lld", &p[i]);
    l = 1, r = 1e18;

    while (l < r)
    {
        long long mid = (l + r) >> 1;
        if (check(mid) <= k) r = mid;
        else l = mid + 1;
    }
    long long tmp;
    if (check(l) != k)
    {
        cout << -1 ;
        return 0;
    }
    else tmp = l;
    l = 1, r = 1e18;
    while (l < r)
    {
        long long mid = (l + r + 1) >> 1;
        if (check(mid) >= k) l = mid;
        else r = mid - 1;
    }
    if (check(l) != k)
    {
        cout << -1 ;
        return 0;
    }
    else cout << tmp << ' ' << l;
    return 0;
}

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

tag:
二分

思路：
将每一个以1开头的片段当作一个整体ki，同时用ki表示当前片段数字的个数，那么若干个ki组合起来的片段的最后一个位置的坐标就是对ki求和Si。所以可以先用二分找到一个大于A的最小值，则A就在那个ki当中，然后求一下A距离上一个ki的偏移量，用A减去S(i - 1)，之后进行判断，如果 == 1则说明A处数字为1，否则就是0。

代码：

#include <iostream>  
#include <cstdio>  
using namespace std;  
int main()  
{  
    int n;  
    scanf("%d", &n);  
    while(n --)  
    {  
        int a;  
        scanf("%d", &a);  
        long long l = 0, r = 1e9;  
        while (l < r)  
        {  
            long long mid = (l + r) >> 1;  
            if (((mid * (mid + 1)) / 2) >= a) r = mid;  
            else l = mid + 1;  
        }  
        l --;  
        long long offset = a - (l * (l + 1)) / 2;  
        if (offset == 1) printf("%d\n", 1);  
        else printf("%d\n", 0);  
    }  
    return 0;  
}