AGC008 D: K-th K
构造长度 N^2 的序列,每个 i 出现 N 次且第 i 个 i 在 x_i;按 x_i 排序后从左右两端贪心填数。来源 AtCoder AGC008 D · 标签 构造 / 贪心 / 排序
题目描述
给定长度为 的序列 ,其中 互不相同。
构造一个长度为 的序列,使 每个数都恰好出现 次,并且数字 的第 次出现位于第 个位置。无解输出 No。
。
题解
先固定每个数的第 次出现在 。
从左到右填数。按 从小到大处理数字 :在 左侧的空位中,从左端开始填入 个 。这样能尽量把位置留给后面 更大的数;如果左侧空位不够,直接无解。
再从右到左填数。按 从大到小处理数字 :在 右侧的空位中,从右端开始填入 个 。同样,如果右侧空位不够则无解。
两步结束后检查所有位置是否都被填满。由于每个数正好需要 个左侧位置和 个右侧位置,全部填满就是合法构造。
复杂度
排序为 ;填数总共处理 个位置。时间为 ,空间为 。
参考
- 题目链接:AtCoder AGC008 D K-th K。