题目背景

曾经发明了信号增幅仪的发明家 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 \geq 0$,则表示写了 $x_i$ 行代码,若 $x_i \lt 0$,则表示删除了 $-x_i$ 行代码。

输出格式

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

输入输出样例

输入 #1

4 2
2
5
-3
9

输出 #1

3 7

说明、提示

  • 对于 $20\%$ 的数据,保证$ l \le 10$。
  • 对于 $40\%$ 的数据,保证 $l \le 100$ 。
  • 对于 $60\%$ 的数据,保证$l \le 2 \times 10^3$。
  • 对于 $100\%$ 的数据,保证 $1 \leq l \le 10^5$,$-10^9 \le x_i \le 10^9$。

分析

显然这是一个“最小值最大“和"最大值最小"的问题,所以我们要通过二分来枚举 $n$ ,然后再代入 $n$ 将得到的值与 $k$ 比较判断是否成立,不成立则将右端向左,成立则将左端向右,使两个端点不断相互逼近最优解即可得到答案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,x[100001],ans_1=-1,ans_2=-1;
int l,r,m;
int check(int a){
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(sum+x[i]<=0)sum=0;
        else sum+=x[i];
        if(sum>=a){
            sum=0;
            cnt++;
        }
    }
    return cnt;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&x[i]);
    }
    l=1,r=1e17;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)<=k){
            r=mid-1;
            if(check(mid)==k){
                ans_1=mid;
            }
        }else l=mid+1;
    }
    l=1,r=1e17;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)>=k){
            l=mid+1;
            if(check(mid)==k){
                ans_2=mid;
            }
        }else r=mid-1;
    }
    if(ans_1==-1){
        printf("%lld",ans_1);
        return 0;
    }
    printf("%lld %lld",ans_1,ans_2);
    return 0;
}
最后修改:2021 年 07 月 05 日 09 : 11 PM
如果觉得我的文章对你有用,请随意赞赏