[UVA] 1016 - Silly Sort

題目連結

題意:

給一個數列，
一次只能做一個交換，
每做一次a b交換，就要將sum加入a跟b，
最後sum要最小，且要把這個數列排序好。
範例輸入:
3 2 1
1跟3交換   1 2 3  ，sum=4

8 1 2 4
1跟2交換  8 2 1 4，sum=3
1跟4交換  8 2 4 1，sum=3+5
1跟8交換  1 2 4 8，sum=3+5+9=17

1 8 9 7 6
1跟6交換 6 8 9 7 1，sum=7
1跟9交換 6 8 1 7 9，sum=7+10
1跟7交換 6 8 7 1 9，sum=7+10+8
1跟8交換 6 1 7 8 9，sum=7+10+8+9
1跟6交換 1 6 7 8 9，sum=7+10+8+9+7=41

--------------------------------------------------

我的作法:

 將數列分成n個cycle，
每個Cycle表示該值要到下一個值的位置，
例如藍色cycle:
6要到8的位置，
8要到7的位置，
7要到9的位置，
9要到6的位置。

取一個值可以讓cycle中的每一個值到正確位置
例如:
取6當交換的元素，
6跟9做交換，9就到正確位置了，
6再繼續跟7做交換，7就到正確位置了，
6再跟8做交換，8就到正確位置，
最後6也會到正確位置。

所以如果用cycle中的最小值去做交換，
那麼sum一定最小。

但是!
如果先把6跟數列中最小值1交換，
再用1去做cycle交換的元素，
最後再把6跟1交換回來，
可能讓sum更小喔!
所以要兩個做判斷去擇優!

--------------------------------------------------

/* 20151009
 * hanting
 * UVa 1016 - Silly Sort
 * C++
 */
#include <iostream>
#include <vector>
#include <algorithm> //sort,min_element
#include <cstring> //memset
using namespace std;
struct node
{
    int num;
    int origPos;
    bool operator<(const node &a)const
    {
        return num<a.num;
    }
};
int main()
{
    int N;
    int caseN=1;
    while(cin>>N and N)
    {
        vector<node> vec(N);
        for(int i=0;i<N;i++)
        {
            cin>>vec[i].num;
            vec[i].origPos=i;
        }
        sort(vec.begin(),vec.end());
        int AllMin=vec[0].num;
        bool visit[N];
        memset(visit,0,sizeof(visit));
        int sum=0;
        for(int i=0;i<N;i++)
        {
            vector<int> Cycle;
            if(visit[i]==false)//i位置這個數字還不是任一cycle的元素
            {
                visit[i]=true;
                Cycle.push_back(vec[i].num);//cycle的第一個元素
                int next=vec[i].origPos;
                while(visit[next]==false)//建立cycle
                {
                    visit[next]=true;
                    Cycle.push_back(vec[next].num);
                    next=vec[next].origPos;
                }
                int CycleMin=*std::min_element(Cycle.begin(),Cycle.end());
                if(2*(CycleMin+AllMin)+(AllMin)*(Cycle.size()-1) >= CycleMin*(Cycle.size()-1) )
                {
                    for(int i=0;i<Cycle.size();i++)
                    {
                        sum+=Cycle[i]+CycleMin;
                    }
                    sum-=CycleMin*2;
                }
                else
                {//若將AllMin跟CycleMin交換再去做Cycle中的轉換總和比較少
                    for(int i=0;i<Cycle.size();i++)
                    {
                        sum+=Cycle[i]+AllMin;
                    }
                    sum+=(CycleMin+AllMin);
                }
            }
        }
        cout<<"Case "<<caseN++<<": "<<sum<<endl<<endl;
    }

    return 0;
}