【问题描述】\r\n 求n个数中第k大的数\r\n【输入形式】\r\n 第一行n k，第二行为n个数，都以空格分开\r\n【输出形式】\r\n 第k大的数\r\n【样例输入】\r\n\r\n10 3\r\n18 21 11 26 12

这是一道编程题。要求输入一个整数n，再输入n个数，其中第一行为n和k，第二行到第n+1行为n个数，均以空格分开，最后输出第k大的数。

给出样例输入：10 3 \n 18 21 11 26 12...

给出样例输出：18

相关问题

问题描述】 求n个数中第k大的数 【输入形式】 第一行n k，第二行为n个数，都以空格分开 【输出形式】 第k大的数 【样例输入】 10 3 18 21 11 26 12 2 9 33 43 28 【样例输出】 28用c++实现

以下是使用快速选择算法（QuickSelect）的 C++ 实现：

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

int quickSelect(vector<int>& nums, int left, int right, int k) {
    int pivot = nums[left];
    int l = left + 1, r = right;
    while (l <= r) {
        if (nums[l] < pivot && nums[r] > pivot) {
            swap(nums[l++], nums[r--]);
        }
        if (nums[l] >= pivot) {
            ++l;
        }
        if (nums[r] <= pivot) {
            --r;
        }
    }
    swap(nums[left], nums[r]);
    if (r - left + 1 == k) {
        return nums[r];
    } else if (r - left + 1 > k) {
        return quickSelect(nums, left, r - 1, k);
    } else {
        return quickSelect(nums, r + 1, right, k - (r - left + 1));
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    cout << quickSelect(nums, 0, n - 1, k) << endl;
    return 0;
}

首先读入 n 和 k，然后读入 n 个数存入 vector nums 中。接着调用 quickSelect 函数，传入 nums、0、n-1 和 k。函数返回第 k 大的数，直接输出即可。

求集合A上的所有等价关系 问题描述 给定一个n(n<=7)元素的集合A，求出A上所有不同的等价关系并显示出来。 输入格式 首先输入元素个数n(n<=7)，回车之后输入集合A，用大括号封闭。 输出格式 输出A上所有的等价关系。使用c++代码形式呈现

好的，以下是一份用 C++ 实现的代码，可以求出集合 A 上所有不同的等价关系：

#include <iostream>
#include <vector>
#include <set>
using namespace std;

void dfs(int cur, int n, vector<int>& v, vector<vector<int>>& res) {
    if (cur == n) {
        res.push_back(v);
        return;
    }
    dfs(cur + 1, n, v, res);
    v.push_back(cur);
    dfs(cur + 1, n, v, res);
    v.pop_back();
}

bool check(vector<vector<int>>& blocks, int n) {
    for (auto& b : blocks) {
        if (b.size() == 0) continue;
        if (b.size() == 1) {
            if (b[0] != n - 1) return false;
            else continue;
        }
        set<int> s;
        for (auto& x : b) {
            s.insert(x);
        }
        if (s.size() != b.size()) return false;
        for (auto& x : b) {
            for (auto& y : b) {
                if (x == y) continue;
                if (x < y) {
                    if (s.find(x * n + y) == s.end()) return false;
                } else {
                    if (s.find(y * n + x) == s.end()) return false;
                }
            }
        }
    }
    return true;
}

vector<vector<int>> getEquivalenceRelations(int n) {
    vector<vector<int>> res;
    vector<int> v;
    dfs(0, n, v, res);
    vector<vector<int>> blocks;
    for (auto& r : res) {
        bool ok = true;
        for (auto& b : blocks) {
            bool flag = true;
            for (auto& x : b) {
                for (auto& y : r) {
                    if (x < y && (x * n + y) % 2 == 0) {
                        flag = false;
                        break;
                    }
                    if (x > y && (y * n + x) % 2 == 0) {
                        flag = false;
                        break;
                    }
                }
                if (!flag) break;
            }
            if (flag) {
                b.insert(b.end(), r.begin(), r.end());
                ok = false;
                break;
            }
        }
        if (ok) {
            blocks.push_back(r);
        }
    }
    vector<vector<int>> ans;
    for (int i = 0; i < (1 << (n * (n - 1) / 2)); i++) {
        vector<vector<int>> blocks_copy = blocks;
        bool flag = true;
        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (i & (1 << (j * (n - 1) + k - (j + 1) * j / 2))) {
                    bool found = false;
                    for (auto& b : blocks_copy) {
                        set<int> s;
                        for (auto& x : b) {
                            s.insert(x);
                        }
                        if (s.find(j) != s.end() && s.find(k) != s.end()) {
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        flag = false;
                        break;
                    }
                }
            }
            if (!flag) break;
        }
        if (flag && check(blocks_copy, n)) {
            ans.push_back(vector<int>());
            for (int j = 0; j < n * (n - 1) / 2; j++) {
                if (i & (1 << j)) {
                    ans.back().push_back(j);
                }
            }
        }
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> res = getEquivalenceRelations(n);
    cout << "共有 " << res.size() << " 个不同的等价关系：" << endl;
    for (auto& r : res) {
        cout << "{";
        for (int i = 0; i < n; i++) {
            cout << "{";
            for (int j = i + 1; j < n; j++) {
                if (find(r.begin(), r.end(), i * n + j) != r.end()) {
                    cout << i << "," << j << ";";
                }
            }
            cout << "}";
        }
        cout << "}" << endl;
    }
    return 0;
}

这个代码的思路是先通过 dfs 枚举出所有可能的元素对，然后对于每个元素对的情况，判断它们是否满足等价关系的定义。最终，输出所有满足等价关系定义的集合。

需要注意的是，对于一个等价关系 R，它可以用一个 n × n 的矩阵表示，其中第 i 行第 j 列的元素为 1 表示 i 和 j 在 R 中等价，为 0 则表示不等价。而一个 n × n 的矩阵需要用 n × (n-1)/2 个元素来表示，因为矩阵中的对角线上的元素都是 1，所以只需要考虑上三角或下三角的元素即可，共有 n × (n-1)/2 个元素。

另外，这个代码的时间复杂度比较高，需要枚举所有可能的等价关系，所以 n 比较大时运行时间会很长。