代码:
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/CDOJ/1260.cpp
下界和上届
下界
仔细观察这些火柴棍,发现数字1花费的火柴是最少的,所以下界是$2*m$
上界
数字8花费的火柴是最多的,所以上界时$7*m$
由上界下界便可确定时候满足题意了。
贪心的思想
首先我们至少需要满足下界,那么我们首先全部放1,发现1其实是个很小的数字,并且首位的优先级是最高的,所以我们不断将高位的1调整为9。
当火柴不够调整的时候,发现只需要添加一根火柴就能将1变成7,所以我们就不断将1变成7。
最后假如还有多余的火柴,此时我们需要分析一下会有多少剩余。
- 假如最后一位是7,我们剩余一根火柴,我们发现最好的方案就是将最后一个7变成4
- 假如最后一位是7,我们剩余两根火柴,我们发现最好的方案就是将最后一个7变成5
- 假如最后一位是7,我们是不可能获得3根火柴的,否则最后一位一定会是9
- 假如最后一位是9,那么我们就倒着将9变成8