#39222: C++ 解題參考


louisvivov11 (louisvivo)

學校 : 國立交通大學
編號 : 154418
來源 : [112.104.139.212]
最後登入時間 :
2024-02-10 02:31:54
c295. APCS-2016-1029-2最大和 -- 2016年10月APCS | From: [112.104.139.212] | 發表日期 : 2024-01-24 15:10

輸入格式固定,將每一個陣列儲存,所需空間就是 O(mn),可以思考如何將 O(mn) 換成 O(m);

O(mn) 的做法就是將所以資訊保留,但這題其實用不到這麼多,因此直接考慮 O(n) 的作法,

  • 利用輸入流,讀一個吃一個,那就讀一個比較一次,留最大值即可;

psuedo code 如下:

arr(n) // 存 n 個最大值

for i = 1 to n

    arr(i) = max element of an array of m elements

    sum += max element

// 剩下就是判斷所有元素能否整除 sum

  • Space Complexity : O(m)
  • Time Complexity : O(nm)
 
ZeroJudge Forum