有输入低于下界矛盾吗

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

下界算出来是 7。数一数 120 种输入里，归并用了不到 7 次就排完的有几种，再报出最坏的那一档，输出「下界/低于下界的个数/最坏」。

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

提交你的答案

请登录后提交答案。

去登录

← 两种排序的最坏比较次数归并离理论极限差几次 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

vector<int> merge_go(const vector<int>& x, int& c) {
    if (x.size() <= 1) return x;
    size_t m = x.size() / 2;
    vector<int> L = merge_go(vector<int>(x.begin(), x.begin() + m), c);
    vector<int> R = merge_go(vector<int>(x.begin() + m, x.end()), c);
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < L.size() && j < R.size()) {
        c++;
        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;
}

int merge_cmp(const vector<int>& a) {   // 归并排序，返回比较次数
    int c = 0;
    merge_go(a, c);
    return c;
}

int ins_cmp(vector<int> a) {            // 插入排序，返回比较次数
    int c = 0;
    for (size_t i = 1; i < a.size(); i++) {
        int x = a[i];
        int j = (int)i - 1;
        while (j >= 0) {
            c++;
            if (a[j] <= x) break;
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
    return c;
}

vector<vector<int>> all_perms() {
    vector<int> p = {0, 1, 2, 3, 4};
    vector<vector<int>> out;
    do { out.push_back(p); } while (next_permutation(p.begin(), p.end()));
    return out;
}

int main() {
    int lower = (int)ceil(log2(120.0));
    int below = -1, worst = -1;
    // TODO: 遍历全部排列：数一数 merge_cmp 低于 lower 的有几种，并记下最大的那个比较次数
    cout << lower << "/" << below << "/" << worst << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

有输入低于下界矛盾吗

更多题目

全部评论