總網頁瀏覽量

2019年4月16日 星期二

第六題：AI-666 賺多少



















解題策略：
1、交易k次，會有2k個數字，所以取出2k個數字的組合
2、相鄰二個數字相減，即為交易一次的金額
3、將所有金額相加得總金額
4、此題需取2、4、6……，2k個數字出來成一陣列，因為不知最大獲利在那一次
5、相關指令：list(combination(陣列,取幾個數字))

Python Code：
張貼者： 於
標籤：

4 則留言:

  1. 匿名2020年1月1日 下午5:47

    這樣的時間複雜度是不會AC的吧
    O(NK) 是正確的，但是有點太慢
    這題有 O(N) 或 O(N log N) 的 greedy 解，也有O(N log C) 的 Aliens 優化解

    回覆刪除
    回覆
    1. 辜德2023年5月27日 晚上9:31

      我不是資工本科出身的，程式可能寫的不好，你講的這些我會再研究的，謝謝您

      刪除
  2. Aestivate2023年5月24日 上午11:51

    作者已經移除這則留言。

    回覆刪除
  3. Aestivate2023年5月24日 上午11:53

    事實上可以發現K越大，每次多賺得越少，凹函數的性質可以用wqs二分搜優化

    回覆刪除

訂閱： 張貼留言 (Atom)