携程9/28笔试第三题讨论

当时做有bug，结果交了卷改了3分钟貌似对了，求dalao们看看对不对

dp遍历数组，每个元素分为取或不取，维护index保存取的元素索引

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

unordered_set<int> index;
double dp(vector<double> nums, int cur, int k) {
    //剩余次数为0
    if (k == 0) {
        double min_i = *min_element(nums.begin(), nums.end());
        double max_i = *max_element(nums.begin(), nums.end());
        return max_i - min_i;
    }
    //从后往前遍历到第一个元素时
    if (cur == 0) {
        double sum = 0;
        index.insert(cur);
        for (auto i : index) sum += nums[i];
        double avl = sum / index.size();
        for (auto i : index) nums[i] = avl;
        double min_i = *min_element(nums.begin(), nums.end());
        double max_i = *max_element(nums.begin(), nums.end());
        index.erase(cur);
        return max_i - min_i;
    }

    double a = dp(nums, cur - 1, k);
    index.insert(cur);
    double b = dp(nums, cur - 1, k - 1);
    index.erase(cur);
    return min(a, b);
}

int main() {
    int n, k, tmp;
    cin >> n >> k;
    vector<double> nums;
    for (int i = 0; i < n; ++i) {
        cin >> tmp;
        nums.push_back(tmp);
    }
    cout << dp(nums, n - 1, k) << endl;

    system("pause");
    return 0;
}