zrj2012-B3-0023

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：一开始有N个货物点，分别在横坐标1~N的位置。每个位置有一些货物。接下来你要布置M个仓库在N个点上，规则是，首先，要让每个点到最近的仓库的距离之和最小，若有多种方案，去字典序最小的方案。
然后仓库会有一个容量C，每个货物点有若干货物，它们会把所有的货物运到离它们最近的仓库去（如果有多个可以任选），但是仓库的货物不能超过C。问满足条件的最小的C。
题目分两个阶段，首先是确定仓库方案，然后是确定C。
C很好弄，只要仓库放置确定后，二分答案贪心即可（这样比较好写）。
至于仓库方案，我这里介绍从马甲那里听来的方法，个人觉得比较好写且靠谱。
这个方法是采取加点式构造：一开始只有M个仓库(若M>N令M=N），剩下的N-M个点，依次加在第M个仓库右边，第M个仓库左边，第M-1个仓库右边，第M-1个仓库左边,......第1个仓库右边，第1个仓库左边，第M个仓库右边，第M个仓库左边，第M-1个仓库右边，第M-1个仓库左边......这样不断循环下去就OK了。

题目大意：一开始有N个货物点，分别在横坐标1~N的位置。每个位置有一些货物。接下来你要布置M个仓库在N个点上，规则是，首先，要让每个点到最近的仓库的距离之和最小，若有多种方案，去字典序最小的方案。

然后仓库会有一个容量C，每个货物点有若干货物，它们会把所有的货物运到离它们最近的仓库去（如果有多个可以任选），但是仓库的货物不能超过C。问满足条件的最小的C。

题目分两个阶段，首先是确定仓库方案，然后是确定C。

C很好弄，只要仓库放置确定后，二分答案贪心即可（这样比较好写）。

至于仓库方案，我这里介绍从马甲那里听来的方法，个人觉得比较好写且靠谱。

这个方法是采取加点式构造：一开始只有M个仓库(若M>N令M=N），剩下的N-M个点，依次加在第M个仓库右边，第M个仓库左边，第M-1个仓库右边，第M-1个仓库左边,......第1个仓库右边，第1个仓库左边，第M个仓库右边，第M个仓库左边，第M-1个仓库右边，第M-1个仓库左边......这样不断循环下去就OK了。