鏈接：https://ac.nowcoder.com/acm/contest/924/H
來源：牛客網

題目描述

農夫JOHN準備把他的 N（1 <= N <= 10,000）頭牛排隊以便于行動。因為脾氣大的牛有可能會搗亂，JOHN想把牛按脾氣的大小排序。每一頭牛的脾氣都是一個在1到100，000之間的整數并且沒有兩頭牛的脾氣值相同。在排序過程中，JOHN可以交換任意兩頭牛的位置。因為脾氣大的牛不好移動，JOHN需要X+Y秒來交換脾氣值為X和Y的兩頭牛。
請幫JOHN計算把所有牛排好序的最短時間。

輸入描述:

第1行： 一個數， N。
第2~N+1行： 每行一個數，第i+1行是第i頭牛的脾氣值。

輸出描述:

第1行： 一個數，把所有牛排好序的最短時間。

示例1

輸入

復制

3
2
3
1

輸出

復制

7

第一次接觸這個概念，一開始沒有什么思路，后來看博客才知道這個東西就是個置換問題。

題意：就是一個亂序的排列通過兩兩置換來達到升序，每次置換所需的價格是兩點權值之和。

思路：首先理解一個亂序排列存在循環節，也就是說其中一坨經過變換可以達到他們的升序應該的位置，與其他的無關

例如升序時：?1 2 3 4 5 6?

? ? ? ?亂序時：??4 6 3 1?2?5??

如上所示，41為一個循環節，256為一個循環節，3為一個循環節

那么對于每一個長度為n循環節的來說最優的策略就是用這n個數中的最小數來進行n-1次變換，

如上6 2 5 ，就是用2先和5換位置，變成6 5 2，再換2和6那么就是2 5 6 正確的順序。

但是其實除了循環節自身進行n-1次置換，還有一種可能最優的策略就是拿一個所有數中最小的數，與循環節里邊的數進行n+1變換，具體自己理解上邊的例子 就是你可以用 1來對上邊的 6 2 5來變換

那么這兩種花費分別為 循環節里的最小的數*（循環節長度-1）+循環節里其他數的和

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 最小的數*（循環節的長度+2）+循環節里所有數之和

具體看代碼自己模擬理解：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<stdlib.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
const int dir[4][2]={0,1,0,-1,1,0,-1,0};
typedef long long ll;
const ll inFF=9223372036854775807;
typedef unsigned long long ull;
using namespace std;
const int maxn=1e4+5;
int c[maxn],vis[maxn];
int sum=0,minn=inff;
struct node
{int val,id;
}a[maxn];
bool cmp(node s,node e)
{return s.val<e.val;
}
int n;
int dfs(int x)
{vis[x]=1;int cnt=1,val=a[x].val;while(!vis[a[x].id]) //a[x].id就是之前的位置，如果被找過，證明這是一個循環節的結束{x=a[x].id;vis[x]=1;val=min(val,a[x].val);cnt++;}int c1=(cnt-2)*val;int c2=(cnt+1)*minn+val;return min(c1,c2);
}
int main()
{cin>>n;sum=0,minn=inff;for(int i=1;i<=n;i++){scanf("%d",&a[i].val);a[i].id=i;c[i]=i;sum+=a[i].val;minn=min(minn,a[i].val);}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++)if(!vis[i]) sum+=dfs(i);cout<<sum<<endl;
}

?

總結

以上是生活随笔為你收集整理的奶牛排序 cow sort 置换群的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。