- 题目大意
有m本书，k个人来抄，每本书有一个书本页数；求使得k个人抄完的最大页数最小，并且每个人都至少要抄一本，然后输出抄书的方案 。
- 解题思路
这是个最大值中的最小值问题，先用二分+贪心算出一个最大页数的最小值(在二分的过程中，我们对于当前考虑的值 x 划分人数的贪心过程中，我们就有flag[i]去标记，这个位置应该划分开即可)。
- 代码
#include<iostream>
#include<cstring>
using namespace std;
const int MAX = 501;
int num[MAX];
bool vis[MAX];
int t, n,g;
int find(long long a)
{
long long sum = 0, count = 1;
memset(vis, false, sizeof(vis));
for (int i = n - 1; i >= 0; i--)
{
sum += num[i];
if (sum > a)
{
count++;
sum = num[i];
vis[i] = true;
}
}
return count;
}
int main()
{
cin >> t;
while (t--)
{
int max = 0;
cin >> n>>g;
long long l = 0, r = 0;
for (int i = 0; i < n; i++)
{
cin >> num[i];
if (num[i] > l)
l = num[i];
r+= num[i];
}
long long m;
while (l < r)
{
m = (l + r) / 2;
if (find(m) <= g)
r = m;
else
{
l = m + 1;
}
}
max=find(r);
for (int i = 0; i < n&&max < g; i++)
{
if (!vis[i])
{
vis[i] = true;
max++;
}
}
cout << num[0];
for (int i = 1; i < n; i++)
{
if (vis[i - 1])
cout << " /";
cout << ‘ ‘ << num[i];
}
cout << endl;
}
return 0;
}