找到将所有 K 数转换为位于 [L,R] 范围内所需的操作数的最佳方法（即 L≤x≤R）

Question

I am solving this question which requires some optimized techniques to solve it. I can think of the brute force method only which requires combinatorics.

Given an array A consisting of n integers. We call an integer "good" if it lies in the range [L,R] (i.e. L≤x≤R). We need to make sure if we pick up any K integers from the array at least one of them should be a good integer.

For achieving this, in a single operation, we are allowed to increase/decrease any element of the array by one.

What will be the minimum number of operations we will need for a fixed k?"

i.e k=1 to n.

input:
L  R
1  2

A=[ 1 3 3 ]

output:
for k=1 : 2 
for k=2 : 1
for k=3 : 0

For k=1, you have to convert both the 3s into 2s to make sure that if you select any one of the 3 integers, the selected integer is good.

For k=2, one of the possible ways is to convert one of the 3s into 2.

For k=3, no operation is needed as 1 is a good integer.

Answer 1

为了确保从中挑选出 k 个元素会给出至少一个有效的方法，您的集合中不应有超过 k-1 个无效的方法。因此，您需要找到使足够多的元素有效的最短方法。我将按如下方式进行：在一次传递中，生成一个映射，计算集合中有多少元素需要 $n$ 操作才能生效。那么，你明明是要取那些操作次数最少的元素，所以取需要操作次数从小到大的元素个数，然后对操作次数求和。

在python中：

def min_ops(L,R,A_set):
    n_ops = dict()  # create an empty mapping
    for a in A_set:   # loop over all a in the set A_set
        n = max(0,max(a-R,L-a))  # the number of operations requied to make a valid
        n_ops[n] = n_ops.get(n,0) + 1  # in the mapping, increment the element keyed by *n* by ones. If it does not exist yet, assume it was 0.
    allret = []   # create a new list to hold the result for all k
    for k in range(1,len(A_set)+1):  # iterate over all k in the range [1,N+1) == [1,N]
        n_good_required = len(A_set) - k + 1
        ret = 0
        # iterator over all pairs of keys,values from the mapping, sorted by key.
        # The key is the number of ops required, the value the number of elements available
        for n,nel in sorted(n_ops.items()):   
            if n_good_required:
               return ret
            ret += n * min(nel,n_good_required)
            n_good_required -= nel
        allret.append(ret)  # append the answer for this k to the result list
    return allret

举个例子：

A_set = [1,3,3,6,8,5,4,7]
L,R = 4,6

对于每个 A，我们找出需要多少操作才能使其有效：

n = [3,1,1,0,2,0,0,1]

（即 1 需要 3 个步骤，3 需要一个，依此类推）然后我们数一数：

n_ops = {
    0: 3,   # we already have three valid elements
    1: 3,   # three elements that require one op
    2: 1,
    3: 1,   # and finally one that requires 3 ops
}

现在，对于每个 k，我们找出集合中需要多少个有效元素，例如对于k = 4，我们最多需要8个集合中的3个无效，所以我们需要5个有效的。

因此：

ret = 0
n_good_requied = 5
with n=0, we have 3 so take all of them
ret = 0
n_good_required = 2
with n=1, we have 3, but we need just two, so take those
ret = 2
we're finished

Answer 2

正如 burnpanck 在他的回答中所解释的那样，为了确保当您选择数组中的任何 k 个元素时，并且至少其中一个元素在 [L,R] 范围内，我们需要确保有数组中 [L,R] 范围内的至少 n - k + 1 个数字。

因此，首先，对于每个元素，我们计算使该元素成为 valid 元素（在 [L,R] 范围内）的成本，并将这些成本存储在数组 cost.

我们注意到：

对于k = 1，最小代价是数组cost的总和。
对于k = 2，最小成本是cost减去最大元素的总和。
对于 k = 3，最小成本是 cost 的总和减去两个最大的元素。

...

所以，我们需要有一个prefixSum数组，第i个位置是排序cost数组从0到第i的总和。

计算prefixSum后，我们可以在O(1)中回答每个k的结果

所以这是 Java 中的算法，注意时间复杂度是 O(n logn):

int[]cost = new int[n];
for(int i = 0; i < n; i++)
    cost[i] = //Calculate min cost for element i
Arrays.sort(cost);
int[]prefix = new int[n];
for(int i = 0; i < n; i++)
   prefix[i] = cost[i] + (i > 0 ? prefix[i - 1] : 0);

for(int i = n - 1; i >= 0; i--)
   System.out.println("Result for k = " + (n - i) + " is " + prefix[i]);

找到将所有 K 数转换为位于 [L,R] 范围内所需的操作数的最佳方法（即 L≤x≤R）

Optimal way to find number of operation required to convert all K numbers to lie in the range [L,R] (i.e. L≤x≤R)

arrays

algorithm

combinatorics