P1182 数列分段 Section II

这种题固有的套路，一看到什么最大值最小，最小值最大。想都不用想，多半是贪心+二分，和前面几道题一样。但是二分的区间一定要设置好！！！就这题而言left=max(a[i],left)为a[1]–a[N]其中的最大值，而right则为所有a[i]的和，如果将left设置为1，第四个点会wa掉，所以做这种题目一定要把区间设置正确。思路：mid=(left+right )/2,然后在最大值的最小值为假定的mid前提下，尽可能多的去选择，如果最后选择的组数<=M，说明我们指定的这个mid太大，或者刚刚好（因为我们是选取最大值的最小值，所以即使这个组数=M，我们仍然去向左边选择更小的。他比M大就更要去左边了，所以，right=mid-1）,如果组数是>M,说明我们选择的这个mid太小，需要向右边扩展，那就让left=mid+1,下面是AC代码：

#include <iostream>
using namespace std;
typedef  long long int ll;
    int main()
    {
        ll  N,M;
        cin>>N>>M;
        ll a[N+1];
        ll left=0,right=0;
        for(int i=1;i<=N;i++) {
            cin >> a[i];
            right += a[i];
            left=max(left,a[i]);
        }
        ll res;
        while(left<=right)
        {
            int mid=(left+right)/2;
            int pre=1;
            int sum=0;
            int count=1;
            for(int i=1;i<=N;i++) //统计当最长的最短距离为mid时，所能分配做多的组
            {
                if(a[i]+sum<=mid)
                {
                    sum+=a[i];
                }
                else
                {
                    sum=a[i];
                    count++;
                }
            }
            if(count<=M)
            {
                res=mid;
                right=mid-1;

            }
            else
            {
                left=mid+1;
            }

        }
        cout<<res;
        return 0;
    }

注意我们里的count最开始一定要设置为1，不信的话你自己设置为0跑一下试试，我水平也很菜，只能贡献到这了，祝大家早日上岸~