算法1
(贪心)
5 2
1 5 9 12 4
先排序
1 4 5 9 12
为了满足题意,以最大为基础,从第二大的开始往前找,找到一个就归零。
1 4 5 0 21
1 4 0 0 26
不需要重新排序,直接把最大的减去它前一个就行了,因为它前一个已经是零了,而且k大于等于0。
答案是26。
时间复杂度
不知道
C++ 代码
#include<bits/stdc++.h>
using namespace std;
long long n,a[99999999];//以防万一
int main(){
cin>>n;
for(int i=1;i<=n;++i){
long long s,k;
cin>>s>>k;
for(int i=1;i<=s;i++)
cin>>a[i];
sort(a+1,a+s+1);
for(int i=s-1,j=1;j<=k;i--,j++){
a[s]+=a[i];
a[i]=0;
}
cout<<a[s]-a[s-1]<<endl;
}
return 0;
}