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;

}