问题描述
p1588相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-11
解法一:模拟
记上方装置长度为 ml, 下方装置长度为 dl. 由于题目给出的数据规模比较小,这题可以直接暴力找答案,比如固定下方装置 driven 的坐标(换而言之以它为参考系),移动上方装置 master 的位置(偏移量 shift 范围为 [-dl, dl] , 正负号代表移动的方向),对应的 master 坐标范围是 [shift, shift + ml) ,而 driven 坐标范围是 [0, dl). 每次进行偏移后,在重合的坐标范围(求交区间 [start, end) )内看高度是否符合要求,如果都能匹配上,则表明此时有这样一个容器能够容纳它们,其长度为两个装置的最大覆盖范围(求并区间 [start, end) )。最终在所有满足条件的容器中,取长度最短的容器,等同于维护并不断更新一个 res 变量即可。
优化思路:这题也可以进一步优化,容器的长度与 shift 有关。将 shift 的变化由 [-dl, dl] 内逐个 +1 递增改成 0, 1, -1, 2, -2... 这样的变化序列,这样一旦找到了合适的 shift 就表明此时的容器长度最短,可以提前终止循环。不过对于此题,数据规模太小,没有必要做这样的常数级优化,还可能增加代码复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <bits/stdc++.h> using namespace std; int main() { string master, driven; while (cin >> master >> driven) { int ml = master.length(), dl = driven.length(), res = ml + dl; for (int shift = -dl; shift <= dl; shift++) { bool matched = true; int start = max(shift, 0), end = min(shift + ml, dl); for (int pos = start; pos < end; pos++) if (master[pos - shift] + driven[pos] - 2 * '0' > 3) matched = false; if (!matched) continue; start = min(shift, 0), end = max(shift + ml, dl); res = min(res, end - start); } cout << res << endl; } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
while True: try: master, driven = input(), input() ml, dl = len(master), len(driven) res = ml + dl for shift in range(-dl, dl + 1): matched = True start, end = max(shift, 0), min(shift + ml, dl) for pos in range(start, end): if ord(master[pos - shift]) + \ ord(driven[pos]) - 2 * ord('0') > 3: matched = False if not matched: continue start, end = min(shift, 0), max(shift + ml, dl) res = min(res, end - start) print(res) except EOFError: break |