博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ4590: [Shoi2015]自动刷题机
阅读量:5316 次
发布时间:2019-06-14

本文共 1179 字,大约阅读时间需要 3 分钟。

【传送门:


简要题意:

  有l秒时间,AC了k道题,给出每秒写的代码行数(行数>0表示写,<0表示删除,如果剩下的行数不够删,则为0),假设行数>=n时能够提交AC一道题,求出n的最小值和最大值


题解:

  两个二分找最大值最小值,判断的时候只要>=mid就提交

  然后对于不存在的情况,只要没有记录过答案就表示不存在


参考代码:

#include
#include
#include
#include
#include
using namespace std;typedef long long LL;LL a[110000];int n;int check(LL x){ LL d=0; int s=0; for(int i=1;i<=n;i++) { d+=a[i]; if(d>=x) s++,d=0; if(d<0) d=0; } return s;}int main(){ int k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); LL l=1,r=1LL<<63-1; LL nn=-1,mid,mm=-1; while(l<=r) { mid=(l+r)/2; int t=check(mid); if(t<=k) { if(t==k) nn=mid; r=mid-1; } else l=mid+1; } l=1,r=1LL<<63-1; while(l<=r) { mid=(l+r)/2; int t=check(mid); if(t>=k) { if(t==k) mm=mid; l=mid+1; } else r=mid-1; } if(nn==-1||mm==-1) printf("-1\n"); else printf("%lld %lld\n",nn,mm); return 0;}

 

转载于:https://www.cnblogs.com/Never-mind/p/8624280.html

你可能感兴趣的文章
bzoj2257
查看>>
http://www.bootcss.com/
查看>>
20145308 《网络对抗》 注入shellcode+Return-to-libc攻击 学习总结
查看>>
如何使用USBWebserver在本机快速建立网站测试环境
查看>>
变量提升
查看>>
jquery-jqzoom 插件 用例
查看>>
查看oracle数据库的连接数以及用户
查看>>
三.野指针和free
查看>>
简单【用户输入验证】
查看>>
python tkinter GUI绘制,以及点击更新显示图片
查看>>
20130330java基础学习笔记-语句_for循环嵌套练习2
查看>>
Spring面试题
查看>>
C语言栈的实现
查看>>
TC SRM 593 DIV1 250
查看>>
SRM 628 DIV2
查看>>
2018-2019-2 20165314『网络对抗技术』Exp5:MSF基础应用
查看>>
SecureCRT的使用方法和技巧(详细使用教程)
查看>>
自建数据源(RSO2)、及数据源增强
查看>>
关于View控件中的Context选择
查看>>
2018icpc徐州OnlineA Hard to prepare
查看>>