UPC 2959: Caoshen like math 这就是个水题

http://acm.upc.edu.cn/problem.php?id=2959

这就是个水题，之所以要写这个题是感觉很有纪念意义

用力看就是盲……
23333333333333333

这个题就是最小交换几次使数组有序，首先想到的竟然是逆序数

但是逆序数是冒泡排序用的，怎么可能最小……！！！！

具体题解是：

先用结构体标记每个元素的位置和内容，然后进行排序

跟原来的数组进行比较，位置不符合，将原数组元素跟本该排好序在这个位置的元素交换

然后二分查找结构体数组里面该元素将坐标更新

就是这样，很无聊……

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <stack>
#include <queue>
#include <vector>
 
const int MAXN = 1000000 + 10;
const double ESP = 10e-8;
const double Pi = atan(1.0) * 4;
const int INF = 0x7fffffff;
const int MOD = 2012;
typedef long long LL;
 
LL gcd(LL a,LL b){
    return b ?gcd(b,a%b): a;
}
using namespace std;
struct P{
    int x;
    int pp;
    bool operator < (const P a)const{
        return x < a.x;
    }
};
int a[MAXN];
P b[MAXN];
int main(){
//    freopen("input.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)){
        for(int i = 0;i < n;i++){
            scanf("%d",&a[i]);
            b[i].x = a[i];
            b[i].pp = i;
        }
        sort(b,b+n);
        int ans = 0;
        for(int i = 0;i < n;i++){
            if(a[i] != b[i].x){
                int pp = b[i].pp;
                int tmp = a[i];
                a[i] = b[i].x;
                a[pp] = tmp;
                P xx;
                xx.x = tmp;
                int x = lower_bound(b,b+n,xx) - b;
                b[x].pp = pp;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

UPC 2959: Caoshen like math 这就是个水题

推荐阅读