链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=655
原题:
Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so calledscribers. The scriber had been given a book and after
several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was
to hire more scribers.
Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books.
Imagine you havembooks (numbered) that may have different number of pages ()
and you want to make one copy of each of them. Your task is to divide these books amongkscribes,. Each book can be assigned
to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numberssuch
thati-th scriber gets a sequence of books with numbers betweenbi-1+1 andbi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore,
our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.
The input consists ofNcases. The first line of the input contains only positive integerN. Then follow the cases. Each case consists of exactly two lines. At the first line, there are
two integersmandk,. At the second line, there are integersseparated
by spaces. All these values are positive and less than 10000000.
For each case, print exactly one line. The line must contain the input successiondivided
into exactlykparts such that the maximum sum of a single part should be as small as possible. Use the slash character (`/') to separate the parts. There must be exactly one space character between any two successive numbers and between
the number and the slash.
If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.
2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
题目大意:
要抄N本书,编号为1,2,3...N, 每本书有1<=x<=10000000页, 把这些书分配给K个抄写员,要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的,求所有书抄完所用的最少时间的分配方案。
分析与总结:
所化的总时间取决于所有抄写员中任务最多的那个,是经典的最大值最小化问题。LRJ《算法入门经典》P151页有介绍:
在这题中,需要注意的是求和时用32位int可能会溢出,所以要用long long.
代码:
/*
* UVa: 714 - Copying Books
* Time: 0.008s
* Author: D_Double
*
*/
#include<cstdio>
#include<cstring>
#define MAXN 505
using namespace std;
int m, k;
long long arr[MAXN], sum, min, ans;
bool vis[MAXN];
inline int divide(long long M){
memset(vis, 0, sizeof(vis));
int cnt=0;
int pos=m-1;
while(pos>=0){
long long sum=0;
bool ok=true;
while(pos>=0 && sum+arr[pos]<=M){
ok=false;
sum += arr[pos];
--pos;
}
if(ok){
return k+1; // 返回一个大于k的数
}
if(pos>=0) vis[pos] = true;
++cnt;
}
return cnt;
}
long long binary(){
long long left=min, right=sum, mid;
while(left<right){
mid = (left+right)>>1;
if(divide(mid)<=k)
right=mid;
else
left=mid+1;
}
return right;
}
inline void output(){
int cnt=divide(ans);
for(int i=0; i<m-1&&cnt<k; ++i)if(!vis[i]){
vis[i]=true;
++cnt;
}
for(int i=0; i<m; ++i){
if(i) printf(" %lld",arr[i]);
else printf("%lld",arr[i]);
if(vis[i]){
printf(" /");
}
}
puts("");
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&k);
sum=0; min=0;
for(int i=0; i<m; ++i){
scanf("%lld",&arr[i]);
sum += arr[i];
if(arr[i]>min) min=arr[i];
}
ans=binary();
output();
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
GBA所需插件
爷爷的js应用复制 用于从SD卡复制到爷爷的HDD的小地图。 固执的老人对电脑不满意
Universal-USB-Installer-1.9.3.6 (将操作系统在安装u盘,从U盘启动安装操作系统ISO) 适用于大部分Linux \windows 操作系统 更新于2013-6-28
|----> COPYING -- 程序版权信息文档。 这些目录下包扩以下的文件: JustForFun | |----> hanoi.c -- 汉诺塔示例 |----> life.c -- 生命游戏 |----> magic.c -- 数字幻方 |----> queens.c -- 皇后问题 |---...
Hot QuickReport TechTip - Copying Preview pages to the Clipboard * Complementary products for QuickReport: - Codwright - Programmer‘s editor - DeLux - Visual Basic to Delphi converter - LlPDFLib - ...
devcpp所需的必须文件。devcpp所需的必须文件。
First the overlay - copying this file to /boot/overlays and adding line "dtoverlay=sdtweak,poll_once" to /boot/config.txt solved the kworker issue with polling the card.
COPYING - the copying license AUTHORS - the original authors --------------------------------------------------------------------------- About this release: MP4Creator is the command line mp4 ...
Oracle Solaris 11.3 Copying and Creating Package Repositories in Oracle Solaris 11.3-104
Oracle Solaris 11.2 Copying and Creating Package Repositories in Oracle Solaris 11.2-70
Oracle Solaris 11.1 Copying and Creating Oracle Solaris11.1 Package Repositories-34
Oracle Solaris 11 Copying and Creating Oracle Solaris11 Package Repositories-32
Welcome to PDFsharp =================== Version Information ------------------- PDFsharp 0.7.345 beta 2 Roadmap to PDFsharp Folders ------------------------...See COPYING.TXT for copyright information.
Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the ...
PostgreSQL(postgresql-14.2-2-windows-x64.exe),适用于Windows系统:PostgreSQL是一种特性非常齐全的自由软件的对象-关系型数据库管理系统(ORDBMS),是以加州大学计算机系开发的POSTGRES,4.2版本为基础的对象...
...\mongo-c-driver\share\mongo-c-driver\COPYING ...\mongo-c-driver\share\mongo-c-driver\NEWS ...\mongo-c-driver\share\mongo-c-driver\README.rst ...\mongo-c-driver\share\mongo-c-driver\THIRD_PARTY_...
软件介绍: AI-Copying Boost 1.0.0.4只适合innostor的U盘加速。开启加速后可以加快PC和U盘间的文件拷贝速度,提高U盘的读写速度。注意:仅支持innostor的U盘,其他主控的不支持。
1.osdrv commands description: The design idea of this catalog is to fulfil the requirement that compiling the same set of source code with two different compilation tool chains. So an extra parameter ...
Copying_a_Maximo_Schema_on_Oracle
A JCL STEOP ABOUT COPYING PDS DATASET.