Contest3145 - the 37th game of 2021 freshman individual training match_ J: Eat radish

//
 problem  J:  Eat radish 
 The time limit : 1.000 Sec   Memory limit : 128 MB
 
 Title Description 
 In a magical country , There is a programming rabbit , It writes a lot of code every day , Various programming languages such as pascal、c、c++、java、basic Wait, it knows like the back of your hand , All kinds of algorithms have been cooked in disorder . Xiaohua is its good friend , Often play with it .
 One day , Xiaohua sent a lot of radishes to the programming rabbit . Programming rabbit is very happy , Decided to share its radish with other rabbits . Xiaohua arrived in total n Bag radish （ Number 1 To n）, There are a certain number of radishes in each bag . There are... Rabbits in total m only , Rabbits are very disciplined , By number 1 To m Line up and get the radishes in turn , Carrots are distributed in order of number from small to large （ That is, the rabbit with small number gets the radish in front , The rabbit with a large number gets the radish at the back , Radish must be divided , There can be no surplus ）, Each rabbit can only receive several consecutive bags of radishes , Each rabbit receives at least one bag of radish , A bag of radish can only be given to a rabbit , You can't give more than two rabbits .
 The programming rabbit hopes that the radish can be divided evenly as much as possible （ Otherwise, the little rabbits will be unhappy ^_^）, That is, it hopes to get the most radishes, and the rabbits have the least radishes . This problem is very simple for programming rabbits , Dear students , Will you ？

 Input 
 The first line is two positive integers n and m, Indicates the number of bags of radish and the number of rabbits .
 The second line is n A positive integer , Indicates the number of radishes in each bag .
 Output 
 The output has only one integer on one line , It means the minimum number of radishes that the rabbit who gets the most radishes can get .

 The sample input  Copy
9 3
1 2 3 4 5 6 7 8 9
 Sample output  Copy
17
 Tips 
 The first 1-5 Give the bag of radish to the first rabbit , The total number is 15 A radish , The first 6-7 Give a bag of radish to the second rabbit , The total number is 13 A radish , The first 8-9 Give the bag of radish to the third rabbit , The total number is 17 A radish , The rabbit with the most radishes got 17 A radish , This is the situation that the most rabbits get the least . If the first 1-4 Give the bag to the first rabbit , total 10 A radish , The first 5-7 Give the bag to the second rabbit for a total of 18 A radish , The first 8-9 Give the bag to the third rabbit , total 17 A radish , So the most rabbits get 18 A radish , Larger than the previous plan , So it's not optimal .

 about 60% The data of ,1<=m<=n<=100, The number of radishes in each bag should not exceed 10.
 about 100% The data of ,1<=m<=n<=100000, The number of radishes in each bag should not exceed 10000.

//
#include<bits/stdc++.h>
using namespace std;

// 1<=m<=n<=100000, The number of radishes in each bag should not exceed 10000 1e5*1e4=1e9 < int
const int MAXN=1e5+6;

int a[MAXN];
int n,m;

bool half( int mid )
{
    int i,sum,cnt;
    sum=cnt=0;

    for( i=0;i<n;i++ )
    {
        if( sum+a[i]<=mid ) sum+=a[i];
        else        { cnt++; sum=a[i]; }
    }
    cnt++;                          //  Not exceeding  mid ||  There is just a bag left  

    if( cnt>m ) return false;       //  There are many piles   There are not enough rabbits 
    else        return true;        //  Less stacking   Detachable pile 
}

int main()
{
    int i,x,y,mid;

    while( ~scanf("%d%d",&n,&m) )
    {
        x=y=0;
        memset( a,0,sizeof( a ) );
    
        for( i=0;i<n;i++ )
        {
            scanf("%d",&a[i]);
            x=max( x,a[i] );
            y+=a[i];
        }

        while( x<y )
        {
            mid=( x+y )>>1;
            if( half( mid ) )   y=mid;      // y=mid  It can also be an endpoint 
            else                x=mid+1;
        }
        printf("%d\n",x);
    }
    return 0;
}

//

Q: How to guarantee the existence   A pile  == mid?
A:
     Reasonably define the initial boundary  + half  Conditions  + while

    01  From the meaning of the title   Reasonably define the initial boundary   Reduce the number of searches  (  Reading comprehension  )

    02 half  Conditions 

        01  If  mid  The small   There are too many piles   Not enough rabbits   Lower bound x == mid+1
        02  If  mid  big   Less stacking   To dismantle the pile   upper bound y == mid

         The final target is   Just exist   A pile  == mid 

    03 while

     During the search   Do exist  cnt<m  The situation of   but  y=mid  Destroy it   The end result can only be  cnt==m

     When  cnt==m  when  x!=y, while  Will continue to look for .

     Only when  cnt==m &&  Just exist   A pile  == mid  when  while  It's over .

    eg.
        0 0 1 1 2 1 1 0 0

    0  Excluded  mid
    1 cnt==m  Of  mid
    2 ans

     Only when  x==y  when  while  The cycle stops   Will output results 

//

eg.
    5 2
    3 2 4 10 7 (26)
    10 26
    10 18
    14 18
    16 18
    16 17
    17 17   //  Approaching left and right 

    // y=mid;  End 
    5 2
    100 1 2 3 4 (110)
    100 110
    100 105
    100 102
    100 101
    100 100 //  Approach left  (  initial x  Namely ans )

    // x=mid+1;  End 
    4 2
    100 1 100 1 (202)
    100 202
    100 151
    100 125
    100 112
    100 106
    100 103
    100 101
    101 101 //  When  x  Don't set up  y  When established  y  It's the result 

    2 2
    100 1 (101)
    100 101
    100 100 //  In extreme cases 

    3 2
    100 150 1 (251)
    100 251 
    ... ...
    151     //