最大中位数竞争性编程问题

Question

给你一个由N个整数组成的数组。现在您可以对其执行一种类型的操作，即选择任何索引 i 并将 ai 递增 1，即 ai=ai+1。通过此操作，您希望最大化中位数。此外，您最多可以应用此操作 K 次。奇数数组的中位数为数组非降序排序后的中间元素

输入： 3 2

1 3 5

输出： 5

输入： 5 5

1 2 1 1 1

输出： 3

我很难理解这个问题，我的想法是，他们要求最大中位数，如果我们只是排序并选择中间元素并将其增加 k。那么它将是最大中位数。我在互联网上看到了一些解决方案，但我无法理解它们。有人可以帮我解决这个问题吗？

Answer 1

这段代码看起来如何？这将重复排序并增加中位数 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;
}

Answer 2

My thoughts are, they have asked for the maximum median and if we just sort and pick the middle element and increase it with k. Then it would be the maximum median.

不一定，因为一旦它递增，该元素很可能就不再是中位数了。考虑示例 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，因此有 2 个元素（我们称之为 m）等于中位数，2 是第一个大于中位数的元素。

为了能够增加至少一个的中位数，我们应该从k中消耗至少m（字面上减去m 来自 k), 理想情况下，将每个等于中位数的元素加 1（包括该元素）-> 2, 2, 2（是的，整个数组将是 1, 1, 2, 2, 2，但再次忽略较小的值），因此现在的中位数是 2.

现在有 3 个元素，全部相等，要将中位数增加 1，我们必须消耗 k 中的 3 个。只要 k 保持乐观，我们就可以继续。
如果k不足以“填补”空缺（当k < m时），我们需要停止，中位数不能再增加了。例如。在前面的示例中，步骤是：k = 5、1, 1, 2、m = 2 -> k = 3、2, 2, 2、m = 3 -> k = 0, 3, 3, 3 -> 最大中位数 = 3;

最大中位数竞争性编程问题

Maximum Median competitive programming question

c++

search

max

binary-search

median