最大值最小化应该是二分法中经典的题目，Copying Books就是一道最大值最小化的题目
题目大致的意思是要抄N本书，编号为1,2,3...N, 每本书有1<=x<=10000000页， 把这些书分配给K个抄写员，要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的，求所有书抄完所用的最少时间的分配方案。
设序列的最大值为max，总的和为sum。很显然序列的最大值在[max，sum]之间，找到了上界和下界就可以二分查找。在每次查找的时候，我们可以尽量向右划分，这样可以使划分的最大值尽量最小。如果小于等于查找的数，r = mid，反之 i = mid + 1。找到了最大值中的最小值之后就可以进行划分，划分时只要反向遍历数组，将每个区间尽量向左划即可。不过要注意用 数据过大，要用long long储存，否则会溢出。
题目可以在UVA上提交，不过UVA测评的速度太慢了，可以在https://vjudge.net这个网站上提交。下面是AC的代码。
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
#include<algorithm>
#include<memory>
#include<limits.h>
using namespace std;
int n,k,m;
int arr[501],ans[501];
int findMid(long long num)
{
long long sum = 0,count1 = 0;
for(int i = 0;i < m;++i)
{
if(count1 > k - 1)
return 0;
sum += arr[i];
if(sum > num)
{
sum = arr[i];
++count1;
}
}
if(count1 > k - 1)
return 0;
return 1;
}
void divid(long long num)
{
long long sum = 0,count1 = 0;
for(int i = m - 1;i >= 0;--i)
if(sum + arr[i] > num)
{
ans[i + 1] = 1;
sum = arr[i];
count1++;
}
else
sum += arr[i];
int i = 1;
while(i < m && count1 < k - 1)
{
if(!ans[i])
ans[i] = count1++;
++i;
}
}
int main()
{
cin >> n;
while(n)
{
memset(arr,0,sizeof(arr));
memset(ans,0,sizeof(ans));
long long sum = 0;
int max1 = INT_MIN;
cin >> m >> k;
for(int i = 0;i < m;++i)
{
cin >> arr[i];
sum += arr[i];
max1 = max(max1,arr[i]);
}
long long i = max1,j = sum + 1,mid;
while(i < j)
{
mid = (i + j) / 2;
if(findMid(mid))
j = mid;
else
i = mid + 1;
}
divid(i);
for(int i = 0;i < m - 1;++i)
{
if(ans[i])
cout << '/' << ' ';
cout << arr[i] << ' ';
}
if(ans[m - 1])
cout << '/' << ' ';
cout << arr[m - 1] << endl;
--n;
}
return 0;
}
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
