《算法竞赛入门经典》部分练习题解
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）来穷举可能的情形。
思路：
- 接收输入
- 诸位对字符进行校验，可以将字符转为数字后判断和是否大于3，也可以通过模式对比
- 对字符串进行偏移，然后重复第二步
字符串偏移的方法是填充前置 0
设两个字符串分别是 2222 和 211112，则偏移后的情况为：
2222
02222
002222
….
000002222
————–
211112
实现完毕提交后WA，多次调试均找不到原因，经过调试发现以下错误：
-
使用 fgets 进行获取输入，最大长度指定为 100，但是发现在处理长输入的时候会产生问题。换用 scanf 后解决。
如果使用 fgets，要注意 fgets 只会读入 count – 1 个字符，也就是说传参时应该传 101（还有一个换行符）而不是 100。否则会造成读取 99 个字符后下一行读取了 1 个字符。 -
只固定对其中一个字符串进行偏移（取两个字符串中较短的字符串），而不是对两个字符串都进行偏移
比如：
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 字符串。
- 偏移长度上限有误，正确的偏移长度上限不是自身字符串长度，而是对比字符串的长度。
代码：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/