AGC032 E: Modulo Pairing
把 2N 个数配成 N 对,最小化 (x+y) mod M 的最大值;排序后二分分段,段内首尾配对。来源 AtCoder AGC032 E · 标签 贪心 / 排序 / 二分 / 取模
题目描述
给定 个整数 ,满足 。把它们分成 对,每对 的权值为
一种配对方案的代价是 对权值的最大值。求最小可能代价。
,。
题解
把 升序排序。
存在一种最优方案,可以分成前后两段:前段内部首尾配对,后段内部首尾配对;前段每对的和小于 ,后段每对的和不小于 。因此可以枚举两段的分界点。
设分界点为 ,预处理函数 calc(l,r) 表示把区间 首尾配对后最大的和。二分找到最小的偶数 ,使得后缀 的每一对和都不小于 。此时
- 前段的代价是
calc(1,p); - 后段的代价是
calc(p+1,2N)-M。
答案为两者的最大值。若某一段为空,忽略该段。
结论来自交换论证:四个有序数 中,交叉配对 不会优于包含配对;把配对改成同一段内的首尾配对不会增大最大值。分界点右移时,后缀每对的和单调不减,因此可以二分。
复杂度
排序为 。二分分界点并检查后缀为 ,总时间为 ,空间为 。