BZOJ4590 Shoi2015 自动刷题机

Description

曾经发明了信号增幅仪的发明家SHTSC又公开了他的新发明：自动刷题机–一种可以自动AC题目的神秘装置。自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序，每秒，自动刷题机的代码生成模块会有两种可能的结果：
A.写了x行代码。
B.心情不好，删掉了之前写的y行代码。（如果y大于当前代码长度则相当于全部删除。）
对于每个OJ所有题目，存在某个固定的长度n>0。一旦自动刷题机在某秒结束时积累了大于等于n行的代码，它就会自动提交并AC此题，然后新建一个文件开始写下一题。SHTSC在某个OJ上跑了一天的自动刷题机，得到了很多条关
于写代码的日志信息。他突然发现自己没有记录这个OJ的n究竟是多少。所幸他通过自己在OJ上的Rank知道了机一共切了k道题。希望你计算n可能的最小值和最大值。

Input

第一行两个整数l，k，表示刷题机的日志一共有l行，一共了切了k题。
第二行l个整数，x1…xl。xi>=0表示写了xi行代码。xi<0表示删除了这道题的-xi行代码。
1<=l,k<=100000，|xi|<=10^9

Output

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

Sample Input

4 2

-3

Sample Output
3 7

//样例1：如果n=2那么刷题机就会切掉3题。但如果n>7刷题机最多只能切1题。考虑n=4发生了什么。

第一秒：刷题机写了2行。

第二秒：刷题机又写了5行，共有7行，提交，自信AC。

第三秒：刷题机删掉了3行，共有0行。

第四秒：刷题机写了9行，共有9行，提交，自信AC。

一共AC了两题。

傻子二分

我mid定义成了int一直在TLE。。。。

 #include<bits/stdc++.h>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 1e15

 LL a[N];

 int n,k;

 LL read(){

   LL ans=,w=;char c=getchar();

   while(!isdigit(c)&&c!='-')c=getchar();

   if(c=='-')c=getchar(),w=-;

   while(isdigit(c))ans=(ans<<)+(ans<<)+c-'',c=getchar();

   return ans*w;

 }

 int check(LL len){

   LL tmp=;int siz=;

   for(int i=;i<=n;i++){

     tmp=max(0ll,tmp+a[i]);

     if(tmp>=len)tmp=,siz++;

   }

   return siz;

 }

 int main(){

   n=read();k=read();

   for(int i=;i<=n;i++)a[i]=read();

   LL l,r,l_line=-,r_line=-;

   l=,r=INF;

   while(l<=r){

     LL mid=(l+r)>>;

     if(check(mid)<=k)r=mid-,l_line=mid;

     else l=mid+;

   }

   l=,r=INF;

   while(l<=r){

     LL mid=(l+r)>>;

     if(check(mid)>=k)l=mid+,r_line=mid;

     else r=mid-;

   }

   if(check(l_line)!=k||check(r_line)!=k)printf("-1");

   else printf("%lld %lld",l_line,r_line);

   return ;

 }

巴特西

BZOJ4590 Shoi2015 自动刷题机【二分】

BZOJ4590 Shoi2015 自动刷题机

Description

Input

Output

Sample Input

最新文章

热门文章

巴特西

BZOJ4590 Shoi2015 自动刷题机 【二分】

BZOJ4590 Shoi2015 自动刷题机

Description

Input

Output

Sample Input

最新文章

热门文章

BZOJ4590 Shoi2015 自动刷题机【二分】