题目描述

有两个长度分别为 n1，n2 的长条，长条每格高度分别为 h 或 2h，呈齿状上下咬合在一起。长条不能调换上下顺序，不能前后翻转。现将两长条装入高度为 3h 的容器内，求容器所需的最小长度。

• 输入

输入包含多组数据，每组第一行是表示下方长条的字符串，第二行是表示上方长条的字符串。字符串只含数字 1 和 2 ，表示每格高度；字符串长度不超过 100。输入到文件末尾结束。

• 输出

对每组数据，输出一行表示容器最小长度的整数。

• 样例输入

211112
2222

• 样例输出

6

简单分析

用字符串存储输入数据。遍历所有组合情况，计算符合题设情形情况的总长度并维护其最小值。

• 输入输出框架

#include<iostream>
#include<string>
int min_fix_length(std::string &a, std::string &b);
int main() {
    std::ios::sync_with_stdio(false);
    std::string a, b; while (std::cin >> a >> b) {
        std::cout << min_fix_length(a, b) << std::endl;
    }
    return 0;
}

• std::ios::sync_with_stdio(false)取消iostream与stdio的同步，从而加快读写速度。

算法分析

容易得知一共有 n1 + n2 种组合。可以遍历字符串 a 和 b 上的每一个位置，从位置开始与另一字符串逐一比对，直到任一到达字符串末尾。

使用迭代器遍历。可以使用下标，但使用下标遍历并不会获得更低的开销。代码如下：

#include<string>
#include<algorithm>
int min_fix_length(std::string &a, std::string &b) {
    auto res_len{a.size() + b.size()};
    for (auto it{a.begin()}; it != a.end(); ++it) {
        auto a_i{it}, b_i{b.begin()};
        bool is_fix{true}; while (a_i != a.end() && b_i != b.end()) {
            if (*a_i++ - '0' + *b_i++ - '0' > 3) {is_fix = false; break;}
        }
        if (is_fix) {
            auto crt_len{std::max(it - a.begin() + b.size(), a.size())};
            if (res_len > crt_len) res_len = crt_len;
        }
    }
    for (auto it{b.begin()}; it != b.end(); ++it) {
        auto a_i{a.begin()}, b_i{it};
        bool is_fix{true}; while (a_i != a.end() && b_i != b.end()) {
            if (*a_i++ - '0' + *b_i++ - '0' > 3) {is_fix = false; break;}
        }
        if (is_fix) {
            auto crt_len{std::max(it - b.begin() + a.size(), b.size())};
            if (res_len > crt_len) res_len = crt_len;
        }
    }
    return res_len;
}

• *a_i++ - '0' + *b_i++ - '0' > 3中，运算优先级顺序是 ++ > * > +/- > >。

• std::max()返回“上层”长度和“下层”长度中的较大值，即当前组合情形的总长度。

注意 a 和 b 左对齐的情况处理了两次，同时没有处理 a 和 b 并排放置的情况。但这并不影响算法的正确性。

算法复杂度

• 空间复杂度

迭代器没有额外空间开销，空间复杂度 O(n1 + n2) 来自输入数据的存储。

• 时间复杂度

算法的时间复杂度表达式为 Sum[0 < i < n1] Min（i， n2）+ Sum[0 < i < n2] Min（i，n1） ，结果约等于 O(n1 * n2) 。

AC 代码

#include<iostream>
#include<string>
#include<algorithm>
int main() {
    std::ios::sync_with_stdio(false);
    std::string a, b; while (std::cin >> a >> b) {
        auto ans{a.size() + b.size()};
        for (auto it{a.begin()}; it != a.end(); ++it) {
            auto a_i{it}, b_i{b.begin()};
            bool is_fix{true}; while (a_i != a.end() && b_i != b.end()) {
                if (*a_i++ - '0' + *b_i++ - '0' > 3) {is_fix = false; break;}
            }
            if (is_fix) {
                auto crt{std::max(it - a.begin() + b.size(), a.size())};
                if (ans > crt) ans = crt;
            }
        }
        for (auto it{b.begin()}; it != b.end(); ++it) {
            auto b_i{it}, a_i{a.begin()};
            bool is_fix{true}; while (a_i != a.end() && b_i != b.end()) {
                if (*a_i++ - '0' + *b_i++ - '0' > 3) {is_fix = false; break;}
            }
            if (is_fix) {
                auto crt{std::max(it - b.begin() + a.size(), b.size())};
                if (ans > crt) ans = crt;
            }
        }
        std::cout << ans << std::endl;
    }
    return 0;
}