题目描述
小C有一个N个数的整数序列，这个序列的中的数两两不同。小C每次可以交换序列中的任意两个数，代价为这两个数之和。小C希望将整个序列升序排序，问小C需要的最小代价是多少？
输入输出格式
输入格式：
第一行，一个整数N。
第二行，N个整数，表示小C的序列。
输出格式：
一行，一个整数，表示小C需要的最小代价。
输入输出样例
说明
数据范围：
对于30%的数据，1<=N<=10；
对于全部的数据，1<=N<=100000，输入数据中的其他整数均为正整数且不超过109。
分析：很显然的贪心。因为每次只能交换两个数，那么每次都拿小的数来交换肯定会更优。但肯定不会这么简单。首先从样例分析，样例中的8,2,7这三个数只要互相交换就可以到达目标位置，也就是说这三个数形成了一个“环”，那么每次就照这样的环，将环中的每一个数归位的最小花费只有两种情况：要么就每次都拿环中最小的数与每一个数相互交换，要么就拿整个序列中最小的数与环中每个数交换。不过要注意，第二种情况交换的时候有一个数会交换两次（可以自己模拟一下），那么肯定就将环中最小的数交换两次最优。具体看代码：
Code:
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<iomanip> #include<algorithm> using namespace std; const int N=1e5+7; int n; bool vis[N]; long long ans; struct Node{ int val,pos; }a[N]; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } bool cmp(Node x,Node y) {return x.val<y.val;} inline void work(int x) { long long tot=0,num=0,minn=1e9+7; while(!vis[x]){ vis[x]=true;tot++; num+=a[x].val; if(a[x].val<minn) minn=a[x].val; x=a[x].pos;} long long a1=num+(tot-2)*minn; long long a2=num+(tot+1)*a[1].val+minn; ans+=min(a1,a2); } int main() { n=read(); for(int i=1;i<=n;i++){ a[i].val=read(); a[i].pos=i;} sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) if(!vis[i]) work(i); printf("%lld",ans); return 0; }