UVaOJ 1588 - Kickdown

问题描述

解法一：模拟

记上方装置长度为 ml, 下方装置长度为 dl. 由于题目给出的数据规模比较小，这题可以直接暴力找答案，比如固定下方装置 driven 的坐标（换而言之以它为参考系），移动上方装置 master 的位置（偏移量 shift 范围为 [-dl, dl] , 正负号代表移动的方向），对应的 master 坐标范围是 [shift, shift + ml) ，而 driven 坐标范围是 [0, dl). 每次进行偏移后，在重合的坐标范围（区间交集）内看高度是否符合要求，如果都能匹配上，则表明此时有这样一个容器能够容纳它们，其长度为两个装置的最大覆盖范围（区间并集）。最终在所有满足条件的容器中，取长度最短的容器，等同于维护并不断更新一个 res 变量即可。

优化思路：这题也可以进一步优化，容器的长度与 shift 有关。将 shift 的变化由 [-dl, dl] 内逐个 +1 递增改成 0, 1, -1, 2, -2... 这样的变化序列，这样一旦找到了合适的 shift 就表明此时的容器长度最短，可以提前终止循环。不过对于此题，数据规模太小，没有必要做这样的常数级优化，还可能增加代码复杂度。

#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;
}

#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;

}

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

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

AOAPC II UVaOJ 字符串