洛谷P4343 [SHOI2015]自动刷题机
? 解题记录 ? ? 洛谷 ? ? 二分答案 ?    2018-10-30 00:01:06    796    0    0

题目描述

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

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

1.写了x行代码

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

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

输入输出格式

输入格式:

 

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

第二行ll个整数x_1,...,x_lxi0表示写了xi行代码,xi<0代表删除了这道题的xi行代码。

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 复制
4 2
2
5
-3
9
输出样例#1: 复制
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;
} 

上一篇: 洛谷P3698 [CQOI2017]小Q的棋盘

下一篇: 洛谷P2545 [AHOI2004]实验基地

796 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航