题目描述 小明每天都不知道吃什么。已知小明吃一顿饭有N道菜可以选择，每道菜都有自己的营养价值a[i]，小明想知道，他今天该如何搭配吃菜，能够尝到营养价值第K小的饭菜组合。当然小明是不可能饿着肚子不吃菜的。 输入 输入一行两个整数N，K。N表示有多少道菜 接下来一行N个整数，表示每道菜的营养价值a[i] 数据保证 1<=N<=2*10^5 1<=K<=min(1*10^6,2^N-1) 1<=a[i]<=10^8 输出 输出一个整数 表示第K小的营养价值组合 样例输入 复制 6 3 1 2 1 3 4 5 样例输出 复制 2 c++

你可以使用快速选择算法来解决这个问题。快速选择算法类似于快速排序，但是它只关注查找第K小的元素。下面是一个C++的实现：

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

int partition(vector<int>& a, int low, int high) {
    int pivot = a[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }

    swap(a[i + 1], a[high]);
    return i + 1;
}

int quickSelect(vector<int>& a, int low, int high, int k) {
    if (low == high) {
        return a[low];
    }

    int pivotIdx = partition(a, low, high);
    int pivotRank = pivotIdx - low + 1;

    if (k == pivotRank) {
        return a[pivotIdx];
    } else if (k < pivotRank) {
        return quickSelect(a, low, pivotIdx - 1, k);
    } else {
        return quickSelect(a, pivotIdx + 1, high, k - pivotRank);
    }
}

int main() {
    int N, K;
    cout << "请输入菜品数量N和要查找的第K小的营养价值组合：" << endl;
    cin >> N >> K;

    vector<int> a(N);
    cout << "请输入每道菜的营养价值：" << endl;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    int result = quickSelect(a, 0, N - 1, K);

    cout << "第K小的饭菜组合的营养价值为：" << result << endl;

    return 0;
}

你可以在控制台输入菜品数量N和要查找的第K小的营养价值组合，然后输入每道菜的营养价值。代码使用快速选择算法快速找到第K小的营养价值组合。时间复杂度为O(N)。

希望能帮到你！如有任何疑问，请随时提问。