CDOJ 1260 火火柴棍数字(二)

代码:

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