AT1218 たのしい家庭菜園

AT1218 たのしい家庭菜園

题目

给定一个序列\(a\),你每次可以交换相邻两个元素,你需要通过一系列操作,使得\(a\)序列不严格单峰,求最小操作次数。

思路

首先,我们设一个\(1\sim n\)的排列,\(p_i\)表示\(a_i\)最终移动到了位置\(p_i\).

则操作次数就是排列\(p\)的逆序对数量.简单证下就是将\(a_i\)移动到一号位,就会产生\(i-1\)个逆序对,\(i-1\)此操作,再考虑\(a_j\)移动到二号位,同理,所以,一次操作对应逆序对数量加一.

然后贪心,从小到大枚举每一个\(a_i\),考虑它放在左边还是右边.

假设我们左边\(1\sim l\),右边\(r\sim n\)已经放置,\(a_i\)要么放\(l+1\),要么放\(r-1\),对比一下两个方案对逆序对产生的贡献.

不论放哪边,\(a_i\)和\(1\sim n\), \(r\sim n\)产生的贡献都是一定的.

区别就在于还没有放置的那些草,我们设集合\(S\)表示还没放的草的下标,对比下\(S\)中大于/小于\(i\)的元素数量即可决策,没有后效性,因此贪心是正确的.

需要注意的是若存在\(i,j\ (i\neq j)\),使得\(a_i=a_j\).若某次操作中使得两个元素相邻了,我们并不需要交换它们,因为交换没有任何意义,所以,贪心的时候应当提前消除相同值的元素的影响.

代码

#include <iostream>
#include <cstdio>
#include <algorithm>

#define int long long
using namespace std;
const int N = 3e5 + 10;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}
struct TreeArray {
	int n;
	int a[N];
	#define lowbit(_) ((_) & -(_))
	void upd(int pos , int dat) {
		for( ; pos <= n ; pos += lowbit(pos))a[pos] += dat;
	}
	int GetSum(int pos) {
		int sum = 0;
		for( ; pos ; pos -= lowbit(pos))sum += a[pos];
		return sum;
	}
	int GetSum(int l , int r) {
		return GetSum(r) - GetSum(l - 1);
	}
} a;

int n;
int h[N];
struct Grass {
	int h , id;
} g[N];
bool cmp(Grass a ,  Grass  b) {
	return a.h != b.h ? (a.h < b.h) : (a.id > b.id);
}
signed main() {
	a.n = n = read();
	for(int i = 1 ; i <= n ; i++)
		g[i].h = read() , g[i].id = i;
	sort(g + 1 , g + n + 1 , cmp);
	for(int i = 1 ; i <= n ; i++)
		a.upd(i , 1);
	long long ans = 0;
	for(int l = 1 ; l <= n ; ) {
		int r = l;
		while(r <= n && g[r].h == g[l].h)a.upd(g[r].id , -1) , ++r;
		for(int i = l ; i < r ; i++)
			ans += min(a.GetSum(g[i].id - 1) , a.GetSum(g[i].id + 1 , n));
		l = r;
	}
	cout << ans << endl;
	return 0;
}