1063 wuli51和京导的毕业旅行

思路

中等题，二分+贪心。

简化题意，将m+1个数字分成n份，ans为这n段中每段数字和的最大值，求ans最小值及其方案。

对于这种求最小的最大值，最常用的方法是二分。答案一定在[0,sum]之间，通过判断是否符合要求可以求得ans。在本题中，ans一定是整数，所以二分过程中left、mid、right也是整数。

如何判断是否符合要求？对于某一mid值，遍历一次露营地距离数组，通过贪心，总是使一天内的行程尽可能接近mid，但不可超过mid。若是加上某一露营地距离超过了mid，代表需要露营一次。最后通过比较露营数cnt与数据要求n-1的大小判断是否符合要求。

那又如何输出方案呢？其实在二分的过程中已经体现了，恰好题目中也是要求前面行程数x尽可能大。所以贪心输出，总是尽可能填满某一天的行程。

贪心还需要注意一个问题，就是输出必须得有n个数，也就是说贪心前得判断一下后面是否有足够的数保准每天都有行程。例如对于n=3，m=2，xi=3,2,1，输出ans应为3，方案应为3,2,1，而不是3,3。

分析

时间复杂度：O(nlgn)。

参考代码

//// Created by AlvinZH on 2017/12/6.// Copyright (c) AlvinZH. All rights reserved.//#include 
    
     int n, m;int sum;//行程总和int D[10005];bool check(int X){    int cnt = 0;    int temp = 0;    for(int i = 1; i <= m; i++)    {        if(D[i] > X) return false;        if(temp + D[i] > X)        {            temp = D[i];            cnt++;        }        else            temp += D[i];    }    return cnt <= n-1;}int MinMaxX()//二分法求得min(max(xi)){    int l = 0, r = sum;    while(l <= r)    {        int mid = (l+r) / 2;        if(check(mid))            r = mid - 1;        else            l = mid + 1;    }    return l;}int main(){    while(~scanf("%d %d", &n, &m))    {        sum = 0;        m += 1;        for(int i = 1; i <= m; i++)        {            scanf("%d", &D[i]);            sum += D[i];        }        int ans = MinMaxX();        printf("%d\n", ans);        int cnt = 0;        int temp = 0;        for(int i = 1; i <= m; i++)        {            if(D[i]+temp > ans || n-1 - cnt > m-i)//无法合并||只剩下m-i段，[i+1~m]            {                printf("%d ", temp);                temp = D[i];                cnt++;            }            else                temp += D[i];        }        printf("%d\n", temp);    }}