自动刷题机_(二分）

原题链接：P4343 [SHOI2015] 自动刷题机 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：存在一种自动刷题机，可以选择两种处理方式，写n行代码或删除n行代码，给出其做题的日志，包括做了多少次操作，AC了多少题，还有每次操作内容，当写到N行代码时，提交并AC，然后开新文件，代码清零，当删除代码数量大于原有数量时，认为清零，要找N的最大值和最小值

思路

有最大最小值，说明存在左右边界

发现当N越大时，AC的题目会越少，存在两个边界值可以AC k道题，即满足题目要求，用二分求解，但是与一般二分不同，要记录刚好刷了 k 道题的答案

当刷了 g道题，g>=k 说明行数定义太少，修改l=mid + 1，意味着当g==k的左边界找到时，还是会修改l，找有边界

相反可以找左边界

judge 函数，计算AC了多少题目，因为数据给的小，可以用迭代累加，当达到AC条件时，清零重新计数

代码

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
 
LL ans1 = -1, ans2 = -1;
LL n, k;
LL a[N];
LL mx;
 
//左右边界问题，还有求解等于的解决
 
LL judge(LL x)
{
    int cnt = 0;
    LL clear = 0;
    for(int i = 1; i <= n; i ++)
    {
        // while(a[i] - a[clear] < x && i <= n) i ++;
        // if(i <= n)
        // {
        //     cnt ++;
        //     clear = i;
        // }
 
        clear = max(clear + a[i], 0LL);
        if(clear >= x) clear = 0, cnt ++;
    }
 
    //if(cnt == k) ans1 = x;
    return cnt;
}
 
 
 
void erfen_m()
{
    LL l = 1, r = mx;
    while(l <= r)
    {
        LL mid = l + r >> 1;
        LL x = judge(mid);
        //小于说明mid太大
        if(x <= k) r = mid - 1;
        else l = mid + 1;
        if(x == k) ans1 = mid;
    }
}
 
 
void erfen_M()
{
    LL l = 1, r = mx;
    while(l <= r)
    {
        LL mid = l + r >> 1;
        LL x = judge(mid);
        if(x >= k) l = mid + 1;
        else r = mid - 1;
        if(x == k) ans2 = mid;
    }
}
 
int main()
{
    cin >> n >> k;
 
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        mx += (a[i] > 0) * a[i];
        //a[i] = max(0LL, a[i] + a[i - 1]);
    }
 
    erfen_m();
    erfen_M();
 
    if(ans1 != -1)
    {
        cout << ans1 << ' '  << ans2 << endl;
    }
    else 
    {
        cout << "-1" << endl;
    }
}