题解：P11229 [CSP-J 2024] 小木棍 - 新思路

· · 题解

一种没人讲的新思路 — 算最小位数+贪心

不论使用哪种思路，都要先将每个数需要的木棍数算出来 这里我用一个 a 数组记录。

数字 0 1 2 3 4 5 6 7 8 9
木棍个数 6 2 5 5 4 5 6 3 7 6

我们发现，任意给定一个数字 x，都能算出 n=x 时 最优解的位数。

具体方法：
假设先用使用木棍最多的 数字8 进行填充，
剩下的木棍数（<7）选择合适的数字填充即可，
如剩下 1 个木棍，则去掉一个 8，换上 1 和 0（或其它可行组合）即可。

int minlen(int x){
  if(x%7 == 0) return x/7;
  else return x/7+1;
}

知道最优解位数以后，就可以开始填充了。

从结果的最高位开始，对于每一位数，i 枚举 0-9：
如果这里填上 i 时，成功使最优解位数变小了 1，说明这里填 i 是正确的。

注意：1.最后一位数就不能贪心了，要选择合适的数。
           2.需要考虑前导 0 问题

Code:

bool firsttime = true;
while(n>7){
  for(int i=0; i<=9; i++)
    if(firsttime && i==0) continue;//第一位数不能为0
    if(minlen(n-a[i]) < minlen(n)){
      cout<<i;
      n-=a[i];//a[i]前面说过，为数字i所需木棍个数
      break;
    }
    firsttime = false;
}
if(n==7) cout<<8<<endl;
if(n==6) cout<<0<<endl;
if(n==5) cout<<2<<endl;
if(n==4) cout<<4<<endl;
if(n==3) cout<<7<<endl;
if(n==2) cout<<1<<endl;

有些聪明的小朋友就会问了：如果剩下 n=1 怎么办呢：
如果 n=1，那么最后两位数就要填 01，不如将它作为 10 放在最前面，结果更小，所以此情况不会发生（除下列特殊情况）。

最后，一定记得特判特殊数据：

具体代码将上面三部分整合即可

upd：@Cow Q: 为什么使位数小1就证明是答案？
A: 因为每次位数都小 1，最终位数 = 正解位数, 而最终位数对的情况下 计算过程会保证数最小。

10.28upd : 本蒟蒻写的时候过于仓促导致代码出现了问题，目前已改正。感谢 @ny_Dacong 的更正与完整AC代码提供