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

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
    对第一个字符串进行偏移时:


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

    有一个长度为 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/

发表评论

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