AGC032 E: Modulo Pairing

把 2N 个数配成 N 对,最小化 (x+y) mod M 的最大值;排序后二分分段,段内首尾配对。

来源 AtCoder AGC032 E · 标签 贪心 / 排序 / 二分 / 取模

题目描述

给定 2𝑁 个整数 𝑎1,…,𝑎2𝑁,满足 0≤𝑎𝑖<𝑀。把它们分成 𝑁 对,每对 (𝑥,𝑦) 的权值为

(𝑥+𝑦)mod𝑀.

一种配对方案的代价是 𝑁 对权值的最大值。求最小可能代价。

1≤𝑁≤105,1≤𝑀≤109。

题解

把 𝑎 升序排序。

存在一种最优方案,可以分成前后两段:前段内部首尾配对,后段内部首尾配对;前段每对的和小于 𝑀,后段每对的和不小于 𝑀。因此可以枚举两段的分界点。

设分界点为 𝑝,预处理函数 calc(l,r) 表示把区间 [𝑙,𝑟] 首尾配对后最大的和。二分找到最小的偶数 𝑝,使得后缀 [𝑝+1,2𝑁] 的每一对和都不小于 𝑀。此时

  • 前段的代价是 calc(1,p);
  • 后段的代价是 calc(p+1,2N)-M。

答案为两者的最大值。若某一段为空,忽略该段。

结论来自交换论证:四个有序数 𝑎≤𝑏≤𝑐≤𝑑 中,交叉配对 (𝑎,𝑐),(𝑏,𝑑) 不会优于包含配对;把配对改成同一段内的首尾配对不会增大最大值。分界点右移时,后缀每对的和单调不减,因此可以二分。

复杂度

排序为 𝑂(𝑁log𝑁)。二分分界点并检查后缀为 𝑂(𝑁log𝑁),总时间为 𝑂(𝑁log𝑁),空间为 𝑂(𝑁)。

参考

源码位置