问题描述
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 |
