二分找最大中最小，最小中最大

题意：一个连续N个数的数组，将它分割为连续的m段，m段中每段的和中有一个最大值，现在使最大值最小：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=100010;
int money[maxn];
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    int left=-1,right=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&money[i]);
        if(left<money[i])
            left=money[i];
        right+=money[i];
    }
    while(left<right)
    {
        int mid=(left+right)/2;
        int cnt=0;
        int cost=0;
        for(int i=1;i<=n;i++)
        {
            if(cost+money[i]>mid)
            {
                cnt++;//划分区间，不包括当前的money[i]
                cost=money[i];
            }
            else
                cost+=money[i];
        }
        cnt++;//最后一个cost值也要占一天
        if(cnt<=m)
            right=mid;
        else
            left=mid+1;
    }
    cout<<right<<endl;
    return 0;
}

相反的使 最小值最大：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 100010;
int money[maxn];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    int left = -1, right = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &money[i]);
        if (left<money[i])
            left = money[i];
        right += money[i];
    }
    while (left<right)
    {
        int mid = (left + right) >>1;
        int cnt = 0;
        int cost = 0;
        for (int i = 1; i <= n; i++)
        {
            if (cost + money[i]>=mid)
            {
                cnt++;//划分区间，不包括当前的money[i]
                cost = 0;
            }
            else
                cost += money[i];
        }
        if (cnt < m)
            right = mid;
        else
            left = mid + 1;
    }
    cout << right-1 << endl;
    return 0;
}