现在的位置: 首页 > 综合 > 正文

XMU-1349-数学+模拟

2013年08月14日 ⁄ 综合 ⁄ 共 1776字 ⁄ 字号 评论关闭
30元程序员衣装优惠券,仅剩3天!点击领取

http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1349

题意:将1, 2, 3, 4, ……,n的顺序打乱,如果需要通过两两交换值得到顺序序列:1,2,3,4,5,……,n,那么最少需要多少次交换?

算法:直接把每个数放到应该的位置,算法复杂度是O(n);

证明:将一个数放到i应该的位置相当于从这个堆中排除了这个数,那么把这个数排除了这个堆,如果不采取这种策略因为始终是需要一步将这个数排除的。

/*
收获:
*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;

const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<31);

const double eps=1e-10;
const double pi=acos(-1.0);

#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))


template<class T> inline T gcd(T a,T b)//NOTES:gcd(
  {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm(
  {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}


typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下,左下,左,左上,上,右上,右,右下。

//******* WATER ****************************************************************

//int v1[MAXN];
//int

vector<int> v;

void swap(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
    return ;
}

int cnt(){
    int ret = 0;
    for(int i = 0; i < v.size(); i ++){
        while(v[i] != i){
            ret ++;
            swap(v[i], v[v[i]]);
        }
    }
    return ret;
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int num;
	scanf("%d", &num);
	while(num --){
	    v.clear();
	    int n;
	    scanf("%d", &n);
	    for(int i = 0; i < n; i++){
	        int tp;
	        scanf("%d", &tp);
	        v.push_back(tp - 1);
	    }
	    //cout<<cnt(v1, v2)<<endl;
	    printf("%d\n", cnt());
	}
	return 0;
	//printf("%.6f\n",(double)clock()/CLOCKS_PER_SEC);
}

30元程>序员衣装优惠券,仅剩3天!点击领取

抱歉!评论已关闭.