,它除以的余数不变。我们直接从小到大枚举,直到当前值除以的余数不存在。
中第一次出现的位置一定是符合其在排列 中的次序的,因为如果 不是第一次出现,我们可以把它放置在后面的任何需要出现的位置。我们检查 中元素是否全部符合这个性质即可。
数组是合法的,那么 这个排列中每个数字按序在 中出现的第一个位置下标是单调递增的,即 中数的首次出现位置应该满足其在 中位置的偏序关系。具体来说,对于 任意下标 ,设 是其在 中首次出现位置,都要满足:
数组,以及每个数字出现的所有位置,方便删除和添加。
实际上从E1的样例可以发现一个性质,就是服务器的最优放置方案是把服务器直接放在那些要通网的房子里,那些不需要通网的房子里放服务器会增加不必要的开销。可以用反证法证明一个服务器放在要通网的房子永远比放在不需要通网的房子更优。我们直接最短路+枚举。
算法的思想,我们不妨试试看,将所有边按边权排序。我们每次遍历一条边,都需要对这条边所连接的两个子图进行合并操作。设这条边的权值是 ,它连接的两个子图是 和 ,
和 中分别有 和 个服务器以及 和 个需要通网的房子。
, ,这表明 中的 个房子需要经过这条边连接到 中的服务器,增加的花费为
, ,这表明 中的 个房子需要经过这条边连接到 中的服务器,增加的花费为
, ,这表明 和 中的房子不需要经过这条边,因为它们可以连接自己连通块内的服务器,这样花费更低,所以这种情况不增加花费。
表示 这个子图中有 个服务器时的最小花费。,其中 就是上面讨论的新增花费。
,,这样每次将图分成两个节点数相等的子图,复杂度是