Part2.3 P4343 自动刷题机 【二分答案】

原题链接：P4343 [SHOI2015]自动刷题机 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：求符合要求的最大值和最小值，即 cnt == k

思路：两个二分答案分别求最大最小，记得特判没有答案得情况

评价：二分板子

 1 #include
 2 using namespace std;
 3 //#define mod 1000000007
 4 typedef long long ll;
 5 ll n,k,a[100005],ans=0;
 6 bool check1(ll mid)
 7 {
 8     ll cnt=0,sum=0;
 9     for(int i=1;i<=n;i++)
10     {
11         sum+=a[i];
12         if(sum>=mid)
13         {
14             cnt++;
15             sum=0;
16         }
17         if(sum<=0) sum=0;
18     }
19     if(cnt==k) ans=1;
20     return cnt>=k;
21 }
22 bool check2(ll mid)
23 {
24     ll cnt=0,sum=0;
25     for(int i=1;i<=n;i++)
26     {
27         sum+=a[i];
28         if(sum>=mid)
29         {
30             cnt++;
31             sum=0;
32         }
33         if(sum<=0) sum=0;
34     }
35     if(cnt==k) ans=1;
36     return cnt<=k;
37 }
38 int main()
39 {
40     scanf("%lld%lld",&n,&k);
41     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
42     ll l=1,r=1e18,al,ar;
43     while(l<r)
44     {
45         ll mid=(l+r)/2;
46         if(check2(mid)) r=mid;
47         else l=mid+1;
48     }
49     al=l;
50     //printf("%lld %lld\n",l,r);
51     l=1,r=1e18;
52     while(l<r)
53     {
54         ll mid=(l+r+1)/2;
55         if(check1(mid)) l=mid;
56         else r=mid-1; 
57     }
58     ar=r;
59     if(ans) printf("%lld %lld",al,ar);
60     else printf("-1");
61     return 0;
62 }