题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4590
一道比较有趣的二分
虽然可以直接看出是二分，但是答案取哪个之还是需要思考一小会的
二分两遍
第一遍找出最小值，如果当前刷题数小于等于要求的数，那么我们需要缩小r，然后记录一下mid
第二遍找出最大值，如果当前刷题数大于等于要求的数，那么我们需要扩大l，然后记录一下mid
最后检查一下Min和Max是否都满足条件，不满足就输出-1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<bits/stdc++.h> #define maxn 100010 #define inf LONG_LONG_MAX/2 #define ll long long using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; ll Max,Min; int a[maxn]; inline int check(ll x){ int num=0; ll now=0; for(int i=1; i<=n; i++){ now+=a[i]; if(now<0)now=0; if(now>=x)num++,now=0; } return num; } int main(){ n=rd(),m=rd(); for(int i=1; i<=n; i++)a[i]=rd(); ll l=1,r=inf; while(l<=r){ ll mid=(l+r)/2; if(check(mid)<=m)r=mid-1,Min=mid; else l=mid+1; } l=1,r=inf; while(l<=r){ ll mid=(l+r)/2; if(check(mid)>=m)l=mid+1,Max=mid; else r=mid-1; } if(check(Min)!=m || check(Max)!=m)puts("-1"); else printf("%lld %lld\n",Min,Max); return 0; } |
