P4343 [SHOI2015]自动刷题机-二分的两种情况

[SHOI2015]自动刷题机

题目背景

曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。

题目描述

自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果：

1.写了 $x$ 行代码
2.心情不好，删掉了之前写的 $y$ 行代码。（如果 $y$ 大于当前代码长度则相当于全部删除。）

对于一个 OJ，存在某个固定的正整数长度 $n$，一旦自动刷题机在某秒结束时积累了大于等于 $n$ 行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 $n$ 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 $k$ 道题，希望你计算 $n$ 可能的最小值和最大值。

输入格式

第一行两个整数 $l,k$，表示刷题机的日志一共有 $l$ 行，一共了切了 $k$ 题。

接下来 $l$ 行，每行一个整数 $x_i$，依次表示每条日志。若 $x_i\ge 0$，则表示写了 $x_i$ 行代码，若 $x_i<0$，则表示删除了 $-x_i$ 行代码。

输出格式

输出一行两个整数，分别表示 $n$ 可能的最小值和最大值。
如果这样的 $n$ 不存在，请输出一行一个整数 $-1$。

样例 #1

样例输入 #1

4 2
2
5
-3
9
1
2
3
4
5

样例输出 #1

3 7
1

#include 
using namespace std;
#define de(x) cout<<x<<" ";
#define Pu puts("");
#define sf(x) scanf("%d",&x);
typedef long long ll;
const int N=1e5+10,mod=100003;
int n, m;
ll an1, an2;
int a[N];
int fun(ll x){
    int res = 0;
    ll t = 0;//这里可能会爆int
    for(int i = 1; i <= n; i++){
        t += a[i];
        if(t < 0){//如果y大于之前的代码长度，则相当于全部删除
            t = 0;
        }else if(t >= x){//注意这里，如果此时代码长度大于x，则说明已经完成一个题目
            res++;
            t = 0;
        }
    }
    return res;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        sf(a[i])
    }
    ll l = 1, r = 1e18, mid;
    int t;
    while(l < r){//找第一个大于等于的值
        mid = (l + r) >> 1;
        t = fun(mid);
        if(t == m){
            r = mid;//注意这里的区别
        }else if(t > m){//此时解决的题目数量多于m,则应该增大每个题目需要代码量
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    an1 = l;

    l = 1, r = 1e18;
    while(l < r){//找第一个大于的值
        mid = (l + r) >> 1;
        t = fun(mid);
        if(t == m){
            l = mid + 1;//注意这里的区别
        }else if(t > m){//此时解决的题目数量多于m,则应该增大每个题目需要代码量
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    an2 = l - 1;
    if(fun(an1) != m) printf("-1\n");
    else{
        de(an1)de(an2)
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63