首页 > 代码库 > SPOJ COWPIC(逆序对变形题)

SPOJ COWPIC(逆序对变形题)

SPOJ COWPIC

题目链接

题意:一个序列,相邻可以交换,问最少交换几次使得变成循环的1-n的其中一种

思路:对于原来正常的变换成1-n而言,答案就是逆序对了,而多了这么一个变形,其实只需要考虑一下,先求出变换成1-n的逆序对,然后如果原序列变成2, 3, 4 ... n, 1的话,等于是在原来的序列上,把每个数字模1加n之后求逆序对,那么对于这个新序列而言,只有原来最大的n变成了1会受影响,那么最大的n原来的逆序对就不在是逆序对,原来不是逆序对的就变成逆序对了,所以只要一开始记录下每个数字的位置,然后在循环一遍,求出对应每个数字+1变成1之后,会增加减少的逆序对统计出来,不断维护最小值即可

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100005;
typedef long long ll;

#define lowbit(x) (x&(-x))

int bit[N];

void add(int x, int v) {
	while (x < N) {
		bit[x] += v;
		x += lowbit(x);
	}
}

int get(int x) {
	int ans = 0;
	while (x) {
		ans += bit[x];
		x -= lowbit(x);
	}
	return ans;
}

int n, c[N], pos[N];

int main() {
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &c[i]);
			pos[c[i]] = i;
		}
		ll ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += i - 1 - get(c[i]);
			add(c[i], 1);
		}
		ll ans2 = ans;
		for (int i = 1; i <= n; i++) {
			ans2 -= pos[i] - 1;
			ans2 += n - pos[i];
			ans = min(ans, ans2);
		}
		printf("%lld\n", ans);
	}
	return 0;
}


SPOJ COWPIC(逆序对变形题)