search

KyrieSu / Code_cpp

0 stars 0 forks source link

002.正整數序列 #2

Open LarryLuTW opened 8 years ago

LarryLuTW commented 8 years ago

內容:

給定一個正整數 n 你的任務是要用最少的操作次數把序列 1, 2, ..., n 中的所有數都變成 0 每次操作可從序列中選擇一個或多個整數 同時減去一個相同的正整數

例如 1, 2, 3 可以同時把 2, 3 同時減 2 得到 1, 0, 1 在把兩個 1 同時減 1 得到 0, 0, 0 操作次數是 2

輸入說明:

一個正整數 n (n <= 10^9)

輸出說明:

輸出最少操作次數

範例輸入:

3

範例輸出:

2
KyrieSu commented 8 years ago

目前想法是如果n為奇數，輸出一定為2，因為只需要減去他們中位數，以中位數切割的前後兩段序列便會一樣，所以只需要兩次。

至於n為偶數....未完待續XD

LarryLuTW commented 8 years ago

若 n = 5 原本 -> 1, 2, 3, 4, 5 後面三個減去 3 -> 1, 2, 0, 1, 2 把 1, 2 減去 1 -> 0, 1, 0, 0, 1 把 1 減去 1 -> 0, 0, 0, 0, 0 總共三次喔~

KyrieSu commented 8 years ago

我好像發現規則了！！！ OUTPUT = log2(n)+1 時間複雜度:O(1)

感覺也可以用DP做～ if n=7, then 1,2,3,4,5,6,7 (1)扣掉中位數4 =>1,2,3,0,1,2,3，所以我們只要在求n=3的個數就好

LarryLuTW commented 8 years ago

嗯嗯對 不過可能不是 O(1) 感覺 log2(n) 的複雜度會是 O(log n)

KyrieSu commented 8 years ago

可是我只需要呼叫function這樣不是只做一次嗎（只需要計算）

LarryLuTW commented 8 years ago

嗯嗯是只做一次阿 但是 log2(n) 本身就不是 O(1) 而且這樣是不是會得到小數?

KyrieSu commented 8 years ago

哦哦~ 所以我會(int)ans!

LarryLuTW commented 8 years ago

其實建議一直除 2 就好了 因為 log2(n) 要算滿久的 他算了很久好不容易求得精確的小數 結果又換回整數有點浪費