Rockdu's Blog

题目描述

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

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

1.写了x行代码

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

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

输入输出格式

输入格式：

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

第二行$l$个整数x_1,...,x_l。xi​≥0表示写了xi​行代码，xi​<0代表删除了这道题的−xi​行代码。

输出格式：

输出两个数a,b，分别代表n可能的最小值和最大值。如果不存在这样的n则输出$-1$。

输入输出样例

4 2
2
5
-3
9

3 7

说明

对于20%的数据，n≤10

对于40%的数据，n≤100

对于 60%的数据，n≤2000

对于 100%，n≤100000,-10^9≤x_i≤10^9

因为n越小限制越来越窄，容易发现切题数随n增加单调不增 。那么我们二分出答案为k的一段区间的左右两端就可以了。一开始没判无解，又读漏题了。

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
int num[maxn], n, k;

int Calc(LL x) {
    LL now = 0;
    int ans = 0;
    for(register int i = 1; i <= n; ++i) {
        now += num[i];
        if(now < 0) now = 0;
        if(now >= x) now = 0, ++ans;
    }
    return ans;
}

LL solve(LL L, LL R) {
    while(L < R - 1) {
        LL mid = L + R >> 1;
        if(Calc(mid) >= k) L = mid;
        else R = mid;
    }
    return L;
}

LL solveMN(LL L, LL R) {
    while(L < R - 1) {
        LL mid = L + R >> 1;
        if(Calc(mid) <= k) R = mid;
        else L = mid;
    }
    return R;
}

int main() {
    scanf("%d%d", &n, &k);
    for(register int i = 1; i <= n; ++i)
        scanf("%d", &num[i]);
    LL ans1 = solveMN(0, 1ll * 1e15);
    LL ans2 = solve(1, 1ll * 1e15 + 1ll);
    if(Calc(ans1) != k)
        return printf("-1"), 0;
    printf("%lld %lld", ans1, ans2);
    return 0;
}