NC20434. [SHOI2015]自动刷题机
描述
输入描述
第一行两个整数l，k，表示刷题机的日志一共有l行，一共了切了k题。第二行l个整数，x1…xl。xi ≥ 0表示写了xi行代码。xi < 0表示删除了这道题的-xi行代码。1 ≤ l,k ≤ 100000，|xi| ≤ 10^9
输出描述
输出两个数a，b。分别代表n可能的最小值和最大值。如果不存在这样的n则输出-1。
示例1
输入:
4 2 2 5 -3 9
输出:
3 7
说明:
//样例1：如果n=2那么刷题机就会切掉3题。但如果n>7刷题机最多只能切1题。考虑n=4发生了什么。C++ 解法, 执行用时: 79ms, 内存消耗: 804K, 提交时间: 2022-03-05 19:14:57
#include<iostream>
using namespace std;
typedef long long ll;
int ln,k,x[100500];
int main(){
ll min,max;
cin>>ln>>k;
for(int i=1;i<=ln;i++) cin>>x[i];
ll findmin();
ll findmax();
min=findmin();
max=findmax();
if(min>max||max<=0||min>1e16) cout<<"-1";
else cout<<min<<" "<<max;
return 0;
}
int count(ll n){
ll sum=0,cnt=0;
for(int i=1;i<=ln;i++){
sum+=x[i];
if(sum<0) sum=0;
if(sum>=n) cnt++,sum=0;
if(cnt>k) return cnt;
}
return cnt;
}
ll findmin(){
ll l=1,r=1e16,mid;
while(l<=r){
mid=(l+r)/2;
if(count(mid)>k) l=mid+1;
else r=mid-1;
}
return l;
}
ll findmax(){
ll l=1,r=1e16,mid;
while(l<=r){
mid=(l+r)/2;
if(count(mid)>=k) l=mid+1;
else r=mid-1;
}
return r;
}