AGC001 F – Wide Swap

题目链接

颓了很久,今天终于写了一道题。

首先直接做就一副不会做的样子。我们可以考虑转化将原数组的下标和权值对调,这样子的话,我们若要使A数组字典序最小,则就需要使对调后的P数组字典序最小,因为权值小的尽量前和前面的权值尽量小是一个意思。然后就变成对P数组有这么一个操作:相邻元素权值差≥K的可以交换。那么暴力就是n^2的了,就是对于每一个i都与j(j>i)比较,如果abs(p_i-p_j)<k,那么就确定了ij的相对顺序。连一条p_i \to p_j的边,这样子连边会连很多边导致复杂度GG,所以需要优化连边。我们考虑倒着加入这个序列,显然 p_i连向(p_{i-k},p_i)\cap (p_i,p_{i+k})。我们只需要分别连向两个区间中下标最小的哪一个,这里采用线段树维护区间最小值。代码并不难实现,主要在于想法吧。然而gery分分钟就秒了

 

One thought on “AGC001 F – Wide Swap

发表评论

电子邮件地址不会被公开。 必填项已用*标注