POJ 3270 【组合数学】

题意：

给长度为N的学列，然后让你通过置换来使其递增。原序列没有相同的数字。

1 ≤ N ≤ 10,000

ai<=100000

思路：

先找到循环，然后根据贪心只有两种比较好的情况，让循环里边最小的数作为循环的起点，或者在循环外边找到最小的数作为置换的起点。

坑点:

wa三次的原因是循环外的那个公式写错...因为最后还是要多换一次的...

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

long long jilu[];

long long xu[];

long long sum[];

long long mmin[];

long long num[];

bool vis[];

bool rel[];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<n;i++){

        scanf("%I64d",jilu+i);

        xu[i]=jilu[i];

    }

    sort(xu,xu+n);

    for(int i=;i<n;i++){

        if(!vis[i]){

            rel[i]=;

            sum[i]=mmin[i]=jilu[i];

            num[i]=;

            int tt=i;

            while(upper_bound(xu,xu+n,jilu[tt])-xu-!=i){

                tt=upper_bound(xu,xu+n,jilu[tt])-xu-;

                vis[tt]=;

                sum[i]+=jilu[tt];

                mmin[i]=min(mmin[i],jilu[tt]);

                num[i]++;

            }

        }

    }

    long long ans=;

    for(int i=;i<n;i++){

        if(rel[i]){

            ans+=min((num[i]-)*mmin[i]+sum[i]-mmin[i],xu[]*num[i]+sum[i]+xu[]+mmin[i]);

        }

    }

    printf("%I64d\n",ans);

}