数列排序(索引排序)

题目:P1327 数列排序

#include iostream
#include cstring
#include algorithm
#include cstdio
using namespace std;

int a[100005];
int idx[100005];
bool vis[100005];

bool cmp(int i, int j) {
    return a[i]  a[j];
}

int dfs(int cur, int cnt) {
    vis[cur] = 1;
    ++cnt;
    if (!vis[idx[cur]])
        return dfs(idx[cur], cnt);
    else 
        return cnt;
}

int main()
{
    int n;
    cin  n;
    for (int i = 0; i  n; ++i) {
        scanf("%d", a[i]);
        idx[i] = i;
    }
    sort(idx, idx+n, cmp);
    int ans = 0;
    for (int i = 0; i  n; ++i) {
        if (!vis[i])
            ans += dfs(i, 0)-1;
    }
    cout  ans  endl;
    system("pause");
    return 0;
}
最新回复(0)
/jishuJk3aJGPJhzB9Y3okSoMdXyLkyflDm_2Bwsh_2Bf8cA_3D_3D4794680
8 简首页