SPOJ COWPIC（逆序對變形題）

SPOJ COWPIC

題目鏈接

題意：一個序列，相鄰可以交換，問最少交換幾次使得變成循環的1-n的其中一種

思路：對於原來正常的變換成1-n而言，答案就是逆序對了，而多了這麼一個變形，其實只需要考慮一下，先求出變換成1-n的逆序對，然後如果原序列變成2, 3, 4 ... n, 1的話，等於是在原來的序列上，把每個數字模1加n之後求逆序對，那麼對於這個新序列而言，只有原來最大的n變成了1會受影響，那麼最大的n原來的逆序對就不在是逆序對，原來不是逆序對的就變成逆序對了，所以只要一開始記錄下每個數字的位置，然後在循環一遍，求出對應每個數字+1變成1之後，會增加減少的逆序對統計出來，不斷維護最小值即可

代碼：

#include 
#include 
#include 
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;
}