8-10 Coping Books uva714

题意：把一个包含m个正整数的序列划分为k个   1<=k<=m<=500的非空连续子序列  使得每个正整数恰好属于一个序列  设第i个序列的各个数之和为 Si   你的任务是让所有的 Si的最大值尽量小   输出用‘/’划分好的序列

输出时 如果有多解 s1尽量小  如果s1相同  s2尽量小。。。。。

求最大值的最小值  

可以采用ida*  

但是ida*毕竟是枚举   效率远不如二分答案来的快

之前有一题最大值的最小值也是用二分答案来写很方便   

最好在输入数据部分 统计L和R  这题R为给出序列的和  L为最大元素     

切记 sum  L R 用long long 

这题难在输出部分 

我的思路和LRJ的一样  反向做一个贪心  最后面的尽量取多  前面就会少

但是出现了 后面划分的太开了 导致剩余括号太多了的问题    可能前面几个子序列都为空了。

LRJ加了一条代码很简单的解决了这个问题

并且 能不递归就不递归方便!

#include<bits/stdc++.h>
using namespace std;
#define N 1001
int n,k;
int a[N];
int ok(int x)
{

    int cnt=0;
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        if(sum+a[i]<=x)
            sum+=a[i];
        else
        {
            cnt++;
            sum=a[i];
            if(cnt>k)return 0;
        }
    }
    if(sum!=0)cnt++;
    if(cnt<=k)return 1;
    return 0;
}

void show(long long x)
{
    long long sum=0;
    int remain=k;
    int last[N];
    memset(last,0,sizeof last);
    for(int i=n;i>=1;i--)
    {
        if(sum+a[i]>x || i<remain )
        {
            last[i]=1;sum=a[i];remain--;
        }
        else sum+=a[i];
    }
    for(int i=1;i<n;i++)
    {
        printf("%d ",a[i]);
        if(last[i])printf("/ ");
    }
    printf("%d
",a[n]);
}

int main()
{
    int cas;cin>>cas;
    while(cas--)
    {
        cin>>n>>k;
        long long tot=0;
        int maxx=-1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            tot+=a[i];
            maxx=max(maxx,a[i]);
        }
      long long L=maxx,R=tot;
        while(L<R)
        {
            int mid=(L+R)/2;
            if(!ok(mid) )L=mid+1;
            else R=mid;
        }
       show(L);
    }
}