列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[tcy]

您好，
想請教B.握手Problem ID: handshake這一題。

我對於題目的理解簡單來說是計算兩兩相減的絕對值總和
所以使用巢狀迴圈
for (i=0;i<n;i++)
{
        for (j=i;j<n;j++)
        {
            if(data>data[j])
            {
               sum+=data;
               sum-=data[j];
            }
       else
       {
               sum-=data;
               sum+=data[j];
       }
        }
}

但上傳判定後判定為超時
有想過其他的方法，例如先排序後再乘上係數後總和
但當天排序只有想到使用bubble sort，雖然知道是O(n^2)，應該和上面的方法一樣沒有多大的幫助

今天才突然想到還有其他如Quicksort O(n log n)，或許關鍵在於這個?

還是有其他更好的解法，懇請版主、版友能不吝賜教，謝謝。

[sagit]

這一題先用內建的sort排序(O(nlogn))，
然後最大的一個乘上n-1，第二大的乘上n-3，
往後的每一項就是再減2，直到最小的一個乘上-(n-1)，
加起來就是答案了。