題目鏈接:?https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1125
?收藏
?關注有N臺機器重量各不相等，現在要求把這些機器按照重量排序，重量從左到右依次遞增。移動機器只能做交換操作，但交換機器要花費一定的費用，費用的大小就是交換機器重量的和。例如：3 2 1，交換1 3后為遞增排序，總的交換代價為4。給出N臺機器的重量，求將所有機器變為有序的最小代價。（機器的重量均為正整數）
Input
第1行：1個數N，表示機器及房間的數量。（2?<=?N?<=?50000) 第2?-?N?+?1行：每行1個數，表示機器的重量Wi。(1?<=?Wi?<=?10^9)
Output
輸出最小代價。
Input示例
3 3 2 1
Output示例
4
首先 ?數據量 并不弱, 5w*10^9 因此 ?必然要用 long long ?第一次沒
寫 過了13組 第二次 成員沒用 longlong 過了18組 ? - . ?- ?
題目大意: ? 既然是交換順序; ?
有兩種思路:
?在所有的 數據當中, ?我們把幾個有關聯（這幾個數交換得到正確位置）的數據放到一起, ?組成一個小組, ?這樣 所有數據, 就分成了 好幾個組 ? ,?
然后 我們 在對每一個組掃描的時候, 每次只會影響到當前這個數所在的小組,對其他小組不會造成影響, ?因此對于每一個小組
有兩種操作實現方式,：
?一個是 直接小組內成員交換, 另一個就是,我們借助另外一個特殊值,用特殊值依次實現交換,(這個值是特殊值,為了使重量最小, 所以這個特殊值必須是 全部數據中 最小的那個) 然后 兩種方式比較 選擇當前小組 中 最合適的方法;
?一是 ?用當前組下 小組內成員進行交換;
?二是 ?借助外力實現, 依次交換；
每次 我們選擇 兩個中最小的方法 比較 ?并且要注意; ?方法二中； 騰位子的 要多交換兩次； for 循環的目的，就是為了解決 多組的問題；
?
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <stdio.h>
#include <algorithm>typedef long long ll;using namespace std;
const int MAXN=50100;
struct mac{ll we;ll col;//位置} a[MAXN];int n;int vis[MAXN];ll pre;
int cmp(mac a,mac b)
{return a.we<b.we;
}
ll change(int i)// 當前狀態下最小換的
{ll sum=0;ll x,y,cont=0;x=a[i].we;y=a[i].col;while(i!=y){sum+=a[y].we;vis[y]=1;y=a[y].col;cont++;}sum=sum+min((cont*x),(pre*(cont+2)+x*2));return sum;
}
int main()
{int i,j;while(cin>>n){memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));for(i=1;i<=n;i++){cin>>a[i].we;a[i].col=i;}sort(a+1,a+n+1,cmp);ll sum=0;pre=a[1].we;for(i=1;i<=n;i++){if(!vis[i]){vis[i]=1;sum+=change(i);}}cout<<sum<<endl;}return 0;
}
123
