CF1692G 2^Sort 题解

发布时间 2023-12-04 18:20:45作者: ShawyYum

题意:

思路:

必要性:

对于任意一个符合条件的区间[l,r],任意相邻两项,满足a_i < 2 * a_{i + 1}(l \le i \le r - 1)。

充分性:

对于任意一个长度为k + 1的区间[l,r],如果任意相邻两项满足a_i < 2 * a_{i + 1}(l \le i \le r - 1),那么该区间即为所求区间。

对于一个长度为k + 1的区间[l,r],如果存在相邻两项满足a_i \ge 2 * a_{i + 1}(l \le i \le r - 1),那么该区间不为所求区间。