UVa 714 抄书（贪心+二分）

题意：把一个包含m个正整数的序列划分成k个非空的连续子序列，使得每个正整数恰好属于一个序列。设第i个序列的各数之和为S（i），你的任务是让所有S（i）的最大值尽量小。

思路：“最大值尽量小”问题。

区间的范围肯定是所有数中最大的一个至所有数之和，我们可以使用二分法来确定这样的一个值x，x尽量小并且每个区间都不大它。

题目要求的是前面的区间尽量小，那我们就需要贪心一下，从右边的数开始分配区间。需要注意的是，如果当前剩下来的待分配区间的数正好等于还要分配的组数，那么前面的几个数每个数都为一个区间。

 1 #include<cstring>
 2 #include<string>
 3 #include<iostream>  
 4 using namespace std;
 5 
 6 const int maxn = 10000000 + 5;
 7 int n, m;
 8 long long _max,left,right,_min;
 9 
10 int a[maxn];
11 int ans[510];
12 
13 
14 bool judge(long long mid)  //判断能否每组都小于等于mid
15 {
16     long long sum = 0;
17     int t = 1;
18     for (int i = n - 1; i >= 0; i--)
19     {
20         if (sum + a[i] > mid)
21         {
22             sum = a[i];
23             t++;
24             if (t > m)  return false;   //需要分的组数大于了给定的m组，返回false
25         }
26         else
27             sum += a[i];
28     }
29     return true;
30 }
31 
32 void solve()
33 {
34     memset(ans, 0, sizeof(ans));
35     ::left = _min, ::right = _max;
36     while (::left <= ::right)
37     {
38         long long mid = (::left + ::right) / 2;
39         if (judge(mid))
40         {
41             ::right = mid - 1;
42         }
43         else ::left = mid + 1;
44     }
45     long long sum = 0;
46     int count = 1;
47     for (int i = n - 1; i >= 0; i--)
48     {
49         if (sum + a[i] > ::left)
50         {
51             sum = a[i];
52             ans[i] = 1;
53             count++;
54         }
55         else
56             sum += a[i];
57         if (m - count == i + 1)   //如果剩下来的值数量正好等于要划分的组数，那么一个数为一组
58         {
59             for (int j = 0; j <= i; j++)
60                 ans[j] = 1;
61             break;
62         }
63     }
64     for (int i = 0; i < n - 1; i++)
65     {
66         cout << a[i] << " ";
67         if (ans[i])  cout << "/ ";
68     }
69     cout << a[n - 1] << endl;
70 
71 }
72 
73 int main()
74 {
75     //freopen("D:\txt.txt", "r", stdin);
76     int t;
77     cin >> t;
78     while (t--)
79     {
80         cin >> n >> m;
81         _min = 0;
82         _max = 0;
83         for (int i = 0; i < n; i++)
84         {
85             cin >> a[i];
86             if (_min < a[i])  _min = a[i];
87             _max += a[i];
88         }
89         solve();
90     }
91     return 0;
92 }