【传送门:】
简要题意:
有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;}