最近回顧貪心才發現，我不是很熟悉這個領域，主要是靠長時間做題經驗培養直覺。
遇到貪心...假設它是貪心題時，首先你要假設遵循一個相對單調的程序就能得到答案，像前一篇就是使用排序，然後想辦法證明它，最直覺的就是數學歸納法。總之，這個領域很活。
這體其實不只一種解法，先來說官解的證明。
為什麼持續消除數量最多的兩數就是對的？可以先假設答案不是這樣，有三數 a, b, c，他們的數量為 x, y, z，且 x <= y <= z。
如果先消除 a, b 各一個，最後可能留下一些 c，
但如果做法改成先消除一個 b 和原本落單的 c，會變成一個 a 落單，可是 x <= z，落單的 a 可以和其他 c 一起消掉。
另一種解法是最多數的數量減去其他數的數量，大概像這樣，證明如下。
首先，把最多的數放到左邊，其他放到右邊，如果左邊比較多，答案就是左邊凸出來的數量。
右邊比較多的話，一定可以把右邊相異顏色兩兩消除，直到右邊比較少。因為紅色是最多的，右邊消除後一定能比左邊矮。
這題乍看之下毫無頭緒，但其實可以從簡單的 case 想起。
假設題目是 AAATTC，G 肯定是答案。
可惜題目不是長這樣，例如 AAATTCGCCC，但如果答案第一個字是 G，標出原本字串位置 AAATTCGCCC，可以發現用 CCC 的答案前面再接一個 G(或AT) 即可。
iThome鐵人賽
看影片追技術