最小值最大化，最大值最小化

问题描述
把一个包含n个正整数的序列划分成m个连续的子序列。设第i个序列的各位上的数之和为S(i)，求所有S(i)的最大值最小是多少？

例子：
序列1 2 3 2 5 4划分为3个子序列的最优方案为 1 2 3 | 2 5 | 4，其中S(1),S(2),S(3)分别为6，7，4，那么最大值为7；
如果划分为 1 2 | 3 2 | 5 4，则最大值为9，不是最小。

每次划分后，所有的序列的S[i]求出来，选择其中的最大值

每一种划分，都对应着一个最大的S[i]

求一种划分方法，使得S[i]的最大值，在所有划分方法中最小

思路，先确定个取值区间，遍历这个区间的每一个值，从大的开始

往小了去，找到最后一个值，能有一个分割的序列，最大值小于它

以下的这个方法，进行了优化，采用了二分搜索，跨步大，速度更快

取最大值和最小值的中间值a，如果能找到一个分割序列满足条件，那么说明这个中间值a可能还不是最小

再对这个中间值a和最小值取中间值b，如果不能找到分割方法，那就扩大，取b和a的中间值，以此类推

#include<iostream>
#include<string>
#include<string.h>
#include<cstdio>
using namespace std;

int A[6] = { 1,2,3,2,5,4 };
int n = 6;
int m = 3;
//是否能把序列划分为每个序列之和不大于x的m个子序列
bool is_max(int x)
{
    //每次往右划分，划分完后，所用的划分次数不大于m-1个即可
    int count = 0, s = 0;
    for (int i = 0; i < n; i++)
    {
        if (s + A[i] > x)  //加上当前的元素的和超过了x，就开始一个新的划分
        {
            count++;//本次划分完毕
            s = A[i];//取一个新的序列
            if (count > m - 1)  //划分次数已经超过m-1
                return false;
        }else//否则将下一个元素划入序列
        {
            s += A[i];//尽量往右多划分，让和尽量大
        }
    }
    return true;
}

int main() {
    int max = A[0],sum= A[0];
    for (int i = 1; i < 6; i++)
    {
        if (A[i] > max)
            max = A[i];
        sum += A[i];
    }
    int l = max, r = sum;
    while (l < r)
    {
        int m = l + (r - l) / 2;
        if (is_max(m)) r = m;
        else l = m + 1;
    }
    cout<<l<<endl;
    return 0;
}

描述
农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000).
但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？
输入
有多组测试数据，以EOF结束。
第一行：空格分隔的两个整数N和C
第二行——第N+1行：分别指出了xi的位置
输出
每组测试数据输出一个整数，满足题意的最大的最小值，注意换行。
样例输入
5 3
1
2
8
4
9
样例输出
3

就是有C头牛有特殊的癖好，他们不能聚在一起，距离越远越好

那么，要控制这些牛相互之间的距离，最有价值的参考点就是最短的两头牛之间的距离

为了达到目的，得让这个最短距离越大越好

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<cstdio>
using namespace std;

int a[100005];
int n, c;
int is_min(int k)
{
    int cnt = 1;
    int tmp = a[0];
    for (int i = 1; i<n; i++)
    {
        if (a[i] - tmp >= k)
        {
            tmp = a[i];
            cnt++;
            if (cnt >= c)//装下c头牛
                return true;
        }
    }
    return false;
}

int main() {
    while (~scanf("%d%d", &n, &c))
    {
        for (int i = 0; i<n; i++)
        {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        /*二分查找*/
        int l = 0, r = a[n - 1];
        int mid;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (is_min(mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", r);
    }
    return 0;
}

写上面这两个题，是因为我最近遇到一个题没怎么看懂题目意思，把题目贴在这，明白上面两个题目的意思，这个题目也是一类的，最大值最小化

Sample Input

3  
5 1  
10 80  
20 20  
30 100  
40 30  
50 10  
5 10  
10 80  
20 20  
30 100   
40 30  
50 10  
5 20  
10 80  
50 10  
20 20  
30 100  
40 30 

Sample Output

100  
50  
48


#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<cstdio>
using namespace std;

const int MAXN = 100000;
const int INF = int(1E9);
struct node {
    int X, Y;
}a[MAXN + 5];
bool cmp(node a, node b) {
    return a.X < b.X;
}
int N, R, b[MAXN + 5], c[MAXN + 5];
//b中存放待分配的人口，c留着接收人口
bool Check(int limit) {
    memset(c, 0, sizeof c);
    int people = 1, home = 1;//两个点,people坐标的点是待移动人口，home坐标的点是接收人口的居民点
    b[people] = a[people].Y;
    while (people <= N && home <= N) {//
        if (abs(a[people].X - a[home].X) > R) {//居民无法分配过去
            if (people > home) {//直接进行下一个居民点的分配
                home++;
            }
            else if (people < home) {//人口未分配结束
                //又离最近的接收点太远（这个点之前的点已经分配好了也就是都满了，人只能去这些已经满了的点 ）
                //本次分配方案失败
                return false;
            }
        }
        else if (b[people] + c[home] > limit) {//b中只能分配一部分到c中
            b[people] = b[people] - (limit - c[home]);
            c[home] = c[home] + (limit - c[home]);
            home++;//下一个居民点 
        }
        else if (b[people] + c[home] <= limit) {//c中可承受b中的所有人口，全部分配过去
            c[home] = c[home] + b[people];
            b[people] = b[people] - b[people];
            people++;
            b[people] = a[people].Y;
        }
    }
    for (int i = 1; i <= N; i++)
        if (b[i]) return false;//如果还有人没有被分配，失败
    return true;
}

void prepare() {
    int left = INF, right = 0;
    scanf("%d%d", &N, &R);
    for (int i = 1; i <= N; i++) {
        scanf("%d%d", &a[i].X, &a[i].Y);
        right = max(right, a[i].Y);
        left = min(left, a[i].Y);
    }
    sort(a + 1, a + N + 1, cmp);
    if (N == 1) {
        printf("%d\n", a[1].Y);
        return;
    }
    while (left < right) {
        int Mid = (left + right) / 2;
        if (Check(Mid)) right = Mid;
        else left = Mid + 1;
    }
    printf("%d\n", right);
}

int main() {
    int T;
    scanf("%d", &T);
    for (int i = 1; i <= T; i++)
        prepare();

    system("pause>nul");
    return 0;
}