曾经发明了信号增幅仪的发明家 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。
4 2
2
5
-3
9
3 7
显然这是一个“最小值最大“和"最大值最小"的问题,所以我们要通过二分来枚举 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
© 允许规范转载