题目传送门(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
#include
#include
#include
#include
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原创, 转载必须以链接形式注明>原文链接<