题目传送门(BZOJ)

题解 :

首先有这样一个常用的结论:
我们给一个数组赋上下标 :
[1, 2, 3, 4, 5, 6]
当只能交换相邻两个数时, 若要把它交换顺序, 比如变成下面这样 :
[3, 1, 2 ,6, 5, 4]
最少的交换次数就是下面这个数列的逆序对个数, 且这个下界是必然有方案可以达到的

题目要求你把序列变成一个单峰的形态, 且两端小中间大
所以我们从小到大移动 IOI 草,
对于现在的一棵 IOI 草 $i$ 它要么放在剩下区间里的最左面, 要么就是最右面,
且放在左右的代价是不一样的 (废话)
我们贪心的选择代价小的一边放, 因为这个草的放置位置并不会对后面草的放置位置产生影响
比如这样的一个序列(样例, 离散化后) :
[1, 6, 3, 4, 2, 5] (num)
[1, 2, 3, 4, 5, 6] (下标)
1 直接放就好啦, 那么现在目标序列是 [1] 这样的,
然后我们要放 2 , 它的下标是 5 ,
那么如果放在左面, 会和还没有放的下标 [3, 4, 2] 产生逆序对
而如果放在右面, 则只会和还没有放的下标 [6] 产生逆序对, 所以我们放在右面
请注意 : 我们这里只考虑了和还没有放的下标产生的逆序对, 因为和放完了的代价已经在之前统计到结果中了
所以, 每个草放置位置不会对它后面要放的产生影响, 故我们的贪心是对的.
具体维护的话, 用两个树状数组一起查询就好啦, 取一个最小值更新答案
请注意, 样例并没有两株草同高的情况, 如果一棵草和当前这棵一样高, 那么在最优情况下它们一定不会互相产生贡献
所以每一堆高度一样的我们一起做就可以了
! 听说 return 0 会让程序在 BZOJ 上变快!

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 300300;struct POINT { int x, id; inline int operator < (const POINT &A) const {return x < A.x;}}a[N];int t1[N], t2[N], n;void fix(int x, int c) { for(int i = x; i; i -= i&-i) t1[i] += c; for(int i = x; i <= n; i += i&-i) t2[i] += c;}int inq(int x) { int res1 = 0, res2 = 0; for(int i = x; i; i -= i&-i) res1 += t2[i]; for(int i = x; i <= n; i += i&-i) res2 += t1[i]; return min(res1, res2);}int main() { long long ans = 0; scanf("%d", &n); for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i].x), a[i].id = i, fix(i, 1); sort(a+1, a+n+1); int j; for(int i = 1; i <= n; i = j) { for(j = i; a[j].x == a[i].x; j ++ ) fix(a[j].id, -1); for(j = i; a[j].x == a[i].x; j ++ ) ans += inq(a[j].id); } printf("%lld\n", ans); return 0;}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<