Copying Books

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=85904#problem/B

题意：

把一个包含m个正整数的序列划分成k个（1<=k<=m<=500）非空的连续子序列，使得每个正整数恰好属于一个序列。设第i个序列的各数之和为s(i)，让所有s(i)的最大值尽量小。

如果划分序列最大值相等，就从第一个划分开始让前面的划分尽量小。

案例：

input

9 3

100 200 300 400 500 600 700 800 900

5 4

100 100 100 100 100

output

100 200 300 400 500 / 600 700 / 800 900

100 / 100 / 100 / 100 100

思路分析：

利用二分法，先找出最大值的可能区间。

因为它要让前面的划分尽量小，那么要利用贪心法从右边开始往前遍历进行划分区间，只要其总和不大于之前所求的最大值，就归到那个区间，同时找出“/”所在的地方。但是只有一个条件还不能找出所有“/”，如例2就只有后面2个“/”，所以加上i==x-1,即可。（x=k-1）

源代码如下：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int m,k,c[505],s[505];
 5 long long M;
 6 bool judge(long long mid)     //判断最大值在左区间还是右区间
 7 {
 8     int sum=0,t=k;
 9     for(int i=0;i<m;i++)
10     {
11         sum+=s[i];
12         if(sum>mid)
13         {
14             i--;
15             sum=0;
16             t--;
17         }
18         if(!t)
19         {
20             if(i!=m-1)return false;
21             else return true;
22         }
23     }
24     return true;
25 }
26 void min_max()
27 {
28     memset(c,0,sizeof(c));
29     long long l,r,mid;
30     int i;
31     l=0;r=M;
32     while(l<r)            //判断最小最大值所在区间
33     {
34         mid=(l+r)/2;
35         if(judge(mid)) r=mid;
36         else l=mid+1;
37     }
38     int sum=0,x=k-1;
39     for(i=m-1;i>=0;i--)        //从右边开始确定划分
40     {
41         sum+=s[i];
42         if(sum>r||i==x-1)
43         {
44             sum=0;
45             c[++i]=1;          //确定“/”的位置
46             x--;
47         }
48     }
49     cout<<s[0];
50     for(i=1;i<m;i++)       
51     {
52         if(c[i])cout<<" /";
53         cout<<" "<<s[i];
54     }
55     cout<<endl;
56 }
57 int main()
58 {
59     int N;
60     cin>>N;
61     while(N--)
62     {
63         M=0;
64         cin>>m>>k;
65         for(int i=0;i<m;i++)
66         {
67             cin>>s[i];
68             M+=s[i];
69         }
70         min_max();
71     }
72     return 0;
73 }