东大oj-1511: Caoshen like math

Worfzyq likes Permutation problems.Caoshen and Mengjuju are expert at these problems . They have n cards,and all of the numbers vi on these cards are different . Because Caoshen doesn't

like disordered permutations,he wants to change the permutation into non-descending

permutation.He defines the operations:every time you can choose two digits casually,and

exchange the positions of them.Caoshen is lazy,he wants to know at least how many operations he

needs to change the permutation into non-descending one?

输入

There are multiple test cases. Each case contains a positive integer n,incicate the number of cards(n<=1000000) . Followed by n positive numbers integers v1,v2,...,vn (1≤vi≤n)

---the value of each card.

输出

Print the minmum operations in a signal line for each test case.

样例输入

51 3 2 5 4

样例输出

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxn = 1e6 + 7;
struct Node{
	int v, i;
}a[maxn];
int size;
int cmp(const void *m, const void *n){
	return ((Node*)m)->v - ((Node*)n)->v;
}
bool vis[maxn];
int dfs(int x){
	vis[x] = true;
	if (vis[a[x].i])return 0;
	else return 1 + dfs(a[x].i);
}
int main(){
	freopen("in.txt", "r", stdin);
	while (~scanf("%d", &size)){
		for (int i = 0; i < size; i++)scanf("%d",& a[i].v), a[i].i = i;
		qsort(a, size, sizeof(Node), cmp);
		memset(vis, 0, sizeof(vis));
		long long int ans = 0;
		for (int i = 0; i < size; i++){
			if (!vis[i])ans += dfs(i);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

巴特西

东大oj-1511: Caoshen like math

输入

输出

样例输入

样例输出

最新文章

热门文章