一,思路:
1.这一题如果纯按贪心思路的话是不行的,例如 10 11 12 13 15 22,k=2,按照纯贪心我们会选 10 11 22,但是这其实并不是最小的,我们可以选 22 15。这个选法明显比上一个小。
2.我们可以遍历 k=x的所有选的方案,首先从极端全选最大值开始,每次最大值少选一个,最小值多选一倍(有点抽象,可以代码结合),这样就能遍历所有情况。
二,代码:
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=2e5+10;
typedef long long ll;ll arr[N];void Solved(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>arr[i];sort(arr+1,arr+n+1);//前缀和for(int i=1;i<=n;i++){arr[i]+=arr[i-1];}//i表示删除最小值的对数,可以从0开始,就是全不删,只删最大值
//n-(k-i)---->其实间接表示删除最大值个个数
//2*i--->删除最小值的个数ll ans=0;for(int i=0;i<=k;i++) ans=max(ans,arr[n-(k-i)]-arr[2*i]);cout<<ans<<endl;
}int main()
{int t;cin>>t;while(t--) {Solved();}return 0;
}