错的那版有几种照样对

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

把五个元素的全部 120 种排列都喂给 msort_bad，数一数有多少种它照样给出了正确结果，输出如 n/120。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 把合并的最后一步补上交付基线归纳步不丢元素 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> msort(const vector<int>& a) {
    if (a.size() <= 1) return a;
    size_t m = a.size() / 2;
    vector<int> L = msort(vector<int>(a.begin(), a.begin() + m));
    vector<int> R = msort(vector<int>(a.begin() + m, a.end()));
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) out.push_back(L[i++]);
        else out.push_back(R[j++]);
    }
    out.insert(out.end(), L.begin() + i, L.end());
    out.insert(out.end(), R.begin() + j, R.end());
    return out;
}

vector<int> msort_bad(const vector<int>& a) {
    // 漏了一句：合并到最后没把左半剩下的接上
    if (a.size() <= 1) return a;
    size_t m = a.size() / 2;
    vector<int> L = msort_bad(vector<int>(a.begin(), a.begin() + m));
    vector<int> R = msort_bad(vector<int>(a.begin() + m, a.end()));
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) out.push_back(L[i++]);
        else out.push_back(R[j++]);
    }
    out.insert(out.end(), R.begin() + j, R.end());
    return out;
}

int main() {
    vector<int> p = {0, 1, 2, 3, 4};
    int n = 0, total = 0;
    do {
        total++;
        // TODO: 错的那版跑出来仍然等于正确版的，n 加 1
    } while (next_permutation(p.begin(), p.end()));
    cout << n << "/" << total << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

错的那版有几种照样对

更多题目

全部评论