ZJU/ZOJ 2002 Copying Books 解题报告

题目大意是给出m本书的书页，要求让k个扫描员来扫描，每个扫描员最少要扫描一本书，求使扫描书页最多的那个扫描员扫描的书页最少的方案，如果有多种方案则输出前面的扫描员扫描的书本较少的方案。

这是一道非常经典的DP题，DP的做法可以参见方奇2000年的国家集训队论文。但对于大数据而言这题更加好的做法是参数搜索，可以将时间复杂度降至O(mlogt)，其中t为复制书稿的最大可能页数和最小可能页数之差。简单地说参数搜索就是利用二分查找来逼近确定一个最优参数值使其能够满足题目条件，就本题而言这一参数值就是扫描书页最多的那个扫描员扫描的书页最少的页数需要使得所需的扫描员不超过m。下界显然是书页数最大的那本书的书页，上界则是第k本到最后一本书的书页数之和。

2997140 2008-07-22 19:03:04 Accepted 2002 FPC 00:00.17 404K IwfWcf@LZOI