NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2020高中組初賽
 B.握手 Problem ID: handshake 超時(TLE)

作者 主題: B.握手 Problem ID: handshake 超時(TLE)  (閱讀 148 次)

tcy

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
B.握手 Problem ID: handshake 超時(TLE)
« 於: 十一月 24, 2020, 11:22:20 pm »

您好,
想請教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

  • 管理員
  • 白金會員
  • *****
  • 文章數: 243
    • 檢視個人資料
Re: B.握手 Problem ID: handshake 超時(TLE)
« 回覆 #1 於: 十一月 25, 2020, 12:56:40 am »

這一題先用內建的sort排序(O(nlogn)),
然後最大的一個乘上n-1,第二大的乘上n-3,
往後的每一項就是再減2,直到最小的一個乘上-(n-1),
加起來就是答案了。
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2020高中組初賽
 B.握手 Problem ID: handshake 超時(TLE)