最大中值竞争规划问题

Question

您将得到一个由N个整数组成的数组。现在您可以对其执行一种类型的操作，即选择任何索引i并以1递增ai，即ai=ai+1。此外，您可以在最多K次应用此操作。奇数大小数组的中值是阵列按非递减顺序排序后的中间元素。

投入:3 2

1 3 5

产出:5

投入:5 5

1 2 1 1

产出:3

我很难理解这个问题，我的想法是，他们要求的是最大中位数，如果我们只是选择中间元素，然后用k来增加它，那么它就是最大的中位数。我在互联网上看到了一些解决方案，但我无法理解。有人能帮我做些什么吗？

Answer 1

我的想法是，他们要求的最大中位数，如果我们只是排序和选择中间元素，并增加它的k，那么它将是最大的中位数。

不完全是，因为一旦它增加，这个元素很可能不再是中位数了。以1, 2, 1, 1, 1为例。中位数是1 (排序：1, 1, 1, 1, 2)，如果将所有k = 5添加到该元素中，您将获得1, 1, 6, 1, 2 -> 1, 1, 1, 2, 6。中位数仍然是1，这是“错误的”。

相反，请尝试以下算法。

• 对N个整数进行排序。一次，在开头，这样您就可以很容易地找到中位数(在N偶数的情况下，它是中间的元素或两个相邻中间元素的平均值)。现在，您可以忘记所有小于中位数的元素(同样，如果N是偶数，则需要保留其中一个元素)。

• 发现第一个元素大于中位数。在前面的示例中，我们将使用1, 1, 2，这样就有两个元素(我们称之为m)等于中位数，而2是第一个大于这个值的元素。

为了能够增加至少一个元素的中位数，我们应该至少从m中消耗k (从k中减去m )，理想情况下，在每个元素中添加一个等于中位数(包括该元素)的-> 2, 2, 2 (是的，整个数组将是1, 1, 2, 2, 2，但再次忽略较小的值)，这样现在的中值是2。

现在有三个元素，都是相等的，要将中位数增加一个，我们必须消耗掉3个k。只要k保持阳性，我们就能继续下去。--

• 如果k不足以“填补”空白(当k < m)，我们需要停止，中位数不能进一步增加。在前面的示例中，步骤是：k = 5、1, 1, 2、m = 2 -> k = 3、2, 2, 2、m = 3 -> k = 0、3, 3, 3 -> max中位数=m = 2

Answer 2

这段代码看上去怎么样？这将重复排序和增加中位数k倍。我添加了一些评论，希望这会有所帮助：

void increase_median(std::vector<int>& values) {
    // make sure things are sorted so we can get the median easily
    std::sort(values.begin(), values.end());

    // the median is the middle element, increment it
    size_t mid_point = values.size() / 2;
    values[mid_point]++;
}

std::vector<int> increment_median_k_times(std::vector<int> values, size_t k) {
    // increment k times
    for (size_t i = 0; i < k; ++i) {
        increase_median(values);
    }
    // one last sort for good measure
    std::sort(values.begin(), values.end());
    return values;
}