首页 > 代码库 > HDU - 1394 Minimum Inversion Number （线段树求逆序数）

HDU - 1394 Minimum Inversion Number （线段树求逆序数）

2024-07-15 01:01:44   232人阅读

Description

The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)

You are asked to write a program to find the minimum inversion number out of the above sequences.
 

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
 

Output

For each case, output the minimum inversion number on a single line.
 

Sample Input

 10
1 3 6 9 0 8 5 7 4 2
 

Sample Output

 16

题意：每次可以将第一个放到最后一个，求这个过程中最小的逆序数和

思路：线段树的点更新，首先读入序列的时候就可以算出一个逆序数，找找比它大的数的个数，

         之后将第一个a[0]放到最后一个的时候，每次减少的是a[0],增加的是(n-a[0]-1)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
using namespace std;
const int MAXN = 5005;
const int ROOT = 1;
const int inf = 0x3f3f3f3f;
// single point updated
struct seg{
	int w;
};

struct segment_tree {
	seg node[MAXN * 4];

	void update(int pos) {
		node[pos].w = node[lson(pos)].w + node[rson(pos)].w;
	}

	void build(int l, int r, int pos) {
		if (l == r) { node[pos].w = 0; return; }
		int m = l + r >> 1;
		build(l, m, lson(pos));
		build(m + 1, r, rson(pos));
		update(pos);
	}

	void modify(int l, int r, int pos, int x, int y) {
		if (l == r) { node[pos].w = 1; return; }
		int m = l + r >> 1;
		if (x <= m) modify(l, m, lson(pos), x, y);
		else modify(m + 1, r, rson(pos), x, y);
		update(pos);
	}

	int query(int l, int r, int pos, int x, int y) {
		if (x <= l && r <= y) return node[pos].w;
		int m = l + r >> 1;
		int res = 0;
		if (x <= m) res += query(l, m, lson(pos), x, y);
		if (y > m) res += query(m + 1, r, rson(pos), x, y);
		return res;
	}

	int remove(int l, int r, int pos, int x) {
		if (l == r) { node[pos].w = 0; return l; }
		int m = l + r >> 1;
		int res;
		if (x < node[lson(pos)].w) res = remove(l, m, lson(pos), x);
		else res= remove(m + 1, r, rson(pos), x - node[lson(pos)].w);
		update(pos);
		return res;
	}
} tree;

int main() {
	int n;
	int a[MAXN];
	while (scanf("%d", &n) != EOF) {
		tree.build(1, n, 1);
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
			cnt += tree.query(1, n, 1, a[i]+1, n);
			tree.modify(1, n, 1, a[i]+1, 1);
		}
		int ans = cnt;
		for (int i = 0; i < n-1; i++) { 
			cnt += (n - 2*a[i] - 1);
			ans = min(ans, cnt);
		}
		printf("%d\n", ans);
	}
	return 0;
}


联系
我们