快乐的一天从AC开始 | 20210627 | CF1541B

题目链接
AC代码

每次看到形如\(a_i + a_j = i + j\)这种公式,总想着把带\(i\)的划到一边,带\(j\)的划到一遍,然后map乱搞。但是这题并不是这样搞的。

注意到一个非常重要的条件,就是\(a\)中元素是不重复的。所以可以用一个数组\(p\)记录\(x\)在\(a\)中的下标。

然后对于每一个\(a_i\),从1开始枚举\(a_j\)的值,在根据\(a_j\)和\(p\)获取其在\(a\)中的下标\(j\),然后就可以判断是否满足条件了。

因为\(i + j \le 2n\),所以单次枚举的次数为\(\dfrac{2n}{a_i}\),总的枚举次数为\(2n \sum_{i = 1}^{n} \dfrac{1}{a_i}\),由于\(a_i\)不重复,所以这是一个调和级数,总的枚举次数为\(O(n \log n)\)。

上一篇:不等式题


下一篇:洛谷 P1445 [Violet]樱花