AGC008 D: K-th K

构造长度 N^2 的序列,每个 i 出现 N 次且第 i 个 i 在 x_i;按 x_i 排序后从左右两端贪心填数。

来源 AtCoder AGC008 D · 标签 构造 / 贪心 / 排序

题目描述

给定长度为 𝑁 的序列 𝑥1,…,𝑥𝑁,其中 𝑥𝑖 互不相同。

构造一个长度为 𝑁2 的序列,使 1,…,𝑁 每个数都恰好出现 𝑁 次,并且数字 𝑖 的第 𝑖 次出现位于第 𝑥𝑖 个位置。无解输出 No。

1≤𝑁≤500。

题解

先固定每个数的第 𝑖 次出现在 𝑥𝑖。

从左到右填数。按 𝑥𝑖 从小到大处理数字 𝑖:在 𝑥𝑖 左侧的空位中,从左端开始填入 𝑖−1 个 𝑖。这样能尽量把位置留给后面 𝑥𝑖 更大的数;如果左侧空位不够,直接无解。

再从右到左填数。按 𝑥𝑖 从大到小处理数字 𝑖:在 𝑥𝑖 右侧的空位中,从右端开始填入 𝑁−𝑖 个 𝑖。同样,如果右侧空位不够则无解。

两步结束后检查所有位置是否都被填满。由于每个数正好需要 𝑖−1 个左侧位置和 𝑁−𝑖 个右侧位置,全部填满就是合法构造。

复杂度

排序为 𝑂(𝑁log𝑁);填数总共处理 𝑂(𝑁2) 个位置。时间为 𝑂(𝑁2+𝑁log𝑁),空间为 𝑂(𝑁2)。

参考

源码位置