题解

思路

一次交换若要提高前 $K$ 项之和，最终一定有某个原来位于前 $K$ 项的元素 $A_i$ 被后面的元素 $A_j$ 替换，且 $i\le K<j$、$A_i<A_j$。

做法

任意可行方案至少要让这两个位置之间发生 $j-i$ 次相邻跨越；反过来，只把这一对元素沿区间移动并交换，恰好用 $j-i$ 次操作就能提高分数。因此答案就是所有满足条件的 $(i,j)$ 中 $j-i$ 的最小值。

将所有位置按 $(A_i,i)$ 的值分组后从小到大扫描，维护已经处理过且位于前 $K$ 项中的最大下标。处理某一组相同值时，先用组内后半段位置查询答案，再把组内前半段位置加入维护结构，这样相同值不会被误认为严格增大。若始终没有候选对则输出 $-1$。

复杂度

排序后时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。