《算法竞赛入门经典》部分练习题解

Warning: Use of undefined constant avatar - assumed 'avatar' (this will throw an Error in a future version of PHP) in /data/htdocs/codeingboy.host.smartgslb.com/blog/wp-content/themes/rnmaterial-2.0/single.php on line 17
CodeingBoy 8月 12, 2017

3-11 换低档装置

题目输入的是两个字符串,且只有1和2,代表这段的高度,因此可以设 Ai 和 Bi 为 i 段的高度,判断 Ai+Bi<=3 即可。由于长条不可分割,所以可以通过添加偏移(在字符串前加 0)来穷举可能的情形。

思路:

  1. 接收输入
  2. 诸位对字符进行校验,可以将字符转为数字后判断和是否大于3,也可以通过模式对比
  3. 对字符串进行偏移,然后重复第二步

字符串偏移的方法是填充前置 0

设两个字符串分别是 2222 和 211112,则偏移后的情况为:

2222
02222
002222
….
000002222
————–
211112

实现完毕提交后WA,多次调试均找不到原因,经过调试发现以下错误:

  1. 使用 fgets 进行获取输入,最大长度指定为 100,但是发现在处理长输入的时候会产生问题。换用 scanf 后解决。
    如果使用 fgets,要注意 fgets 只会读入 count – 1 个字符,也就是说传参时应该传 101(还有一个换行符)而不是 100。否则会造成读取 99 个字符后下一行读取了 1 个字符。
  2. 只固定对其中一个字符串进行偏移(取两个字符串中较短的字符串),而不是对两个字符串都进行偏移
    比如:
    21221
    1112212212212211
    对第一个字符串进行偏移时:

    21221
    1112212212212211
    3234
    
    021221
    1112212212212211
    1324
    
    0021221
    1112212212212211
    11334
    
    00021221
    1112212212212211
    1114
    
    000021221
    1112212212212211
    11124
    
    0000021221
    1112212212212211
    11122334
    
    00000021221
    1112212212212211
    1112214
    
    000000021221
    1112212212212211
    11122124
    
    0000000021221
    1112212212212211
    11122122334
    
    00000000021221
    1112212212212211
    1112212214
    
    000000000021221
    1112212212212211
    11122122124
    
    0000000000021221
    1112212212212211
    11122122122334
    
    00000000000021221
    1112212212212211
    1112212212214
    
    000000000000021221
    1112212212212211
    11122122122124
    
    0000000000000021221
    1112212212212211
    1112212212212232
    19
    
    00000000000000021221
    1112212212212211
    1112212212212213
    20
    

    最小长度为 19,。
    调换后:

    21221
    1112212212212211
    3234
    
    21221
    01112212212212211
    22333
    17
    
    21221
    001112212212212211
    21332
    18
    
    21221
    0001112212212212211
    21232
    19
    
    21221
    00001112212212212211
    21222
    20

    有一个长度为 17 的方案。
    调换对比字符串的本质是向前移动 A 字符串。
     

  3. 偏移长度上限有误,正确的偏移长度上限不是自身字符串长度,而是对比字符串的长度。

代码:https://github.com/CodeingBoy/Exercises-on-BeginningAlgorithmContests/blob/master/Chapter%203/3-11.c

本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。
本文链接:https://blog.codeingboy.me/%e3%80%8a%e7%ae%97%e6%b3%95%e7%ab%9e%e8%b5%9b%e5%85%a5%e9%97%a8%e7%bb%8f%e5%85%b8%e3%80%8b%e9%83%a8%e5%88%86%e7%bb%83%e4%b9%a0%e9%a2%98%e8%a7%a3/

发表评论

电子邮件地址不会被公开。 必填项已用*标注