※ 引述《bleed1979 (十三)》之銘言： : 以下這個方法只是能AC，但不代表恆正確，也可能是錯的。 : 解這題的基本認知︰ : 1.測資的正負是一樣的，所以一開始要轉正來解。 : 2.相鄰兩步數最少會差一步，2和3最小可能是+1或-1。 : 3.0，0 + 1 = 1， 0 + 1 + 2 = 3， 0 + 1 + 2 + 3 = 6， : 0 + 1 + 2 + 3 + 4 = 10， 0 + 1 + 2 + 3 + 4 + 5 = 15， : 0 + 1 + 2 + 3 + 4 + 5 + 6 = 21， : 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 : 為0，1，3，6，10，15，21，28.... : 0不要看，依序是奇奇偶偶奇奇偶偶奇奇偶偶.... : 解題，數據觀察。 : 1 2 3 最大為6 : + + + 6 : + + - 0 : + - + 4 : + - - 4 取絕對值，以下皆是。 : - + + 4 : - + - 2 : 推到這就可以發現，最大為6，但0，2，4，6通包了。 : 1 2 3 4 5 最大15 : + + + + + 15 : + + + - + 7 : + + + - - 3 : + + - + + 9 : + + - + - 1 : + + - - - 9 : + - + + + 11 : + - - + + 5 : - + + + + 13 : 我跳著推，但推到這就發現，最大為15，但1，3，5，7，9，11，13，15通包了。 : 到此階段可以合理的假設。總和如果是奇數，從1開始的奇數會包含。 : 同理如偶數。 其實這是可以證明的 若 1+2+...+n = K 是奇數 則 -1+2+3+...+n = K-2 1-2+3+...+n = K-4 1+2-3+...+n = K-6 ... 1+2+3+...-n = K-2n -1+2+3+...-n = K-2n-2 1-2+3+...-n = K-2n-4 ... 依此類推即知 [-K,K] 當中的所有奇數都包了 K 是偶數時同理 : 所以，我的作法就是用for迴圈一直加總， : 跳出迴圈的條件為總和大於測資且測資%2和總和%2相等。 : 有人可能會說，如果找14呢？ : 14相當於15差兩步(5 + 2 = 7)(基礎知識1) 或是 : 加總到7(15, 21, 28)(基礎知識3) : 都是7步。 : Bleed 我這題送 ACM 10025 的做法是建表 ______ 建出一個 1~n 的總和表 n 建到 45000 (比 √2*10^9 稍大) 然後找和時就二分搜尋 再往後找奇偶相等的就是了 因為二分搜尋的關係 往後找頂多找個三四步 所以還滿快的 但意外的在這個地方也可以過... (這裡和 ACM 不一樣是一次執行一組測資 這種的寫法會比 Bleed 的稍慢) -- "LPH" is for "Let Program Heal us".... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.84