MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1588 - Kickdown
AOAPC II

UVaOJ 1588 - Kickdown

Chai
2021-11-24 0:00:00在线评测阅读 280

问题描述

p1588

原题链接:UVaOJ 1588 - Kickdown

相关说明:本题为《算法竞赛入门经典(第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 就表明此时的容器长度最短,可以提前终止循环。不过对于此题,数据规模太小,没有必要做这样的常数级优化,还可能增加代码复杂度。

C++
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;
}
Python
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

AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz