You are given an array a1,a2,…,an1,2,…,, 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.
The first line contains one integer t (1≤t≤1041≤≤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⋅1053≤≤2⋅105; 1≤k≤999991≤≤99999; 2k<n2<) — the number of elements and operations, respectively.
- the second line contains n integers a1,a2,…,an1,2,…, (1≤ai≤1091≤≤109; all ai are different) — the elements of the array.
Additional constraint on the input: the sum of n does not exceed 2⋅1052⋅105.
For each test case, print one integer — the maximum possible sum of elements in the resulting array.
21 11 3 62 46 3999999986
In the first testcase, applying the first operation produces the following outcome:
- two minimums are 11 and 22; removing them leaves the array as [5,10,6][5,10,6], with sum 2121;
- a maximum is 1010; removing it leaves the array as [2,5,1,6][2,5,1,6], with sum 1414.
2121 is the best answer.
In the second testcase, it's optimal to first erase two minimums, then a maximum.
//Maximum Sum //利用前缀和维护数组的总和 //枚举每一种情况 #include <bits/stdc++.h> #define int long long using namespace std; const int N=3e5+10,mod=1e9+7; int n,t,a[N],f[N],res,num,ans,m,s[N]; bool vis[N]; signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>t; while(t--){ res=0; cin>>n>>num; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; for(int i=0;i<=num;i++){ res=max(res,s[n-num+i]-s[2*i]); } cout<<res<<endl; } return 0; }