You are given an array a1,a2,…,an, where all elements are different. You have to perform exactly k operations with it. During each operation, you do exactly one of the following two actions (you choose which to do yourself): find two minimum elements in the array, and delete them; find the maximum element in the array, and delete it. You have to calculate the maximum possible sum of elements in the resulting array. Input The first line contains one integer t (1≤t≤104) — the number of test cases. Each test case consists of two lines: the first line contains two integers n and k (3≤n≤2⋅105; 1≤k≤99999; 2k<n) — the number of elements and operations, respectively. the second line contains n integers a1,a2,…,an (1≤ai≤109; all ai are different) — the elements of the array. Additional constraint on the input: the sum of n does not exceed 2⋅105. Output For each test case, print one integer — the maximum possible sum of elements in the resulting array.
时间: 2023-06-18 11:04:39 浏览: 66
这是一道贪心算法的题目。我们可以将数组 a 排序,然后每次操作时,选择最小的两个元素进行删除,或者选择最大的元素进行删除。根据贪心的思想,我们应该优先选择最小的元素进行删除,因为这样可以保留更多的大元素,从而获得更大的总和。因此,我们可以考虑使用一个小根堆来维护当前数组中最小的两个元素,每次操作时,从堆中取出最小的两个元素进行删除,并将删除后的元素插入堆中。当堆中元素个数不足两个时,我们就从数组中选择最大的元素进行删除。
具体实现时,我们可以使用一个变量 sum 记录当前数组中所有元素的总和,使用一个变量 min_sum 记录当前堆中最小的两个元素的和,使用一个变量 max_num 记录当前数组中最大的元素。每次操作时,如果堆中元素不足两个,就删除最大的元素,否则就从堆中取出最小的两个元素进行删除。删除元素时,需要将 sum 减去被删除元素的值,并将删除后的元素插入堆中。最终,返回 sum 减去 min_sum 即可。
时间复杂度为 O(k log n)。
相关问题
Unable to perform assignment because the left and right sides have a different number of elements.
This error typically occurs when you try to assign values to variables or elements in a list or array, but the number of values on the left side of the assignment operator does not match the number of values on the right side.
For example, if you have a list of three elements and you try to assign four values to it like this:
my_list = [1, 2, 3]
my_list[0:3] = [4, 5, 6, 7]
You will get the error message because the number of values on the right side (4) does not match the number of elements on the left side (3).
To fix this error, make sure that the number of values on the left and right sides of the assignment operator match. If necessary, you may need to add or remove elements from the list or array before assigning new values to it.
You need to be root to perform this command.
This message typically means that the user account you are currently using does not have the necessary permissions to execute the command you are trying to run. In order to perform the command, you will need to either log in as the root user or use the "sudo" command to temporarily elevate your privileges.
For example, you can try running the command with "sudo" prefix like this:
```
sudo <command>
```
You will then be prompted to enter your user password before the command is executed with elevated privileges. However, be careful when using the "sudo" command as it can potentially cause harm to your system if used improperly.