【题解】自动刷题机
自动 题解 刷题
2023-06-13 09:13:01 时间
题目背景
曾经发明了信号增幅仪的发明家 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 将得到的值与 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
© 允许规范转载