C. RationalLee 思维题
文章目录
题意
给你n个数字,要求把它们分成k组,每组w[i]个,ans为每组的最小值加最大值的总和。
思路
很容易看出,如果一组只有一个人,那么把尽可能较大的分给他,最小值和最大值都会大,ans也会大,所有我们先把大的数分给那些只有一个人的组。
考虑剩下的情况,现在每组的最大值都是确认的(较大的每组一个),那么我们需要把每组的最小值尽可能地提高,所以我们依次把一个最大值,w[cnt]-1个小值分给cnt号组,cnt从k到1,这样就能使之后的组的最小值尽可能高。
AC代码
include<iostream>
include<algorithm>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int t,n,k;
int a[maxn],w[maxn];
ll ans;
int main()
{
cin>>t;
while(t--){
cin>>n>>k;
ans=0;
for(int i=1;i<=n;i++)
cin>>a\[i\];
for(int i=1;i<=k;i++)
cin>>w\[i\];
sort(a+1,a+1+n);
sort(w+1,w+1+k);
int cnt=1;
while(w\[cnt\]==1){
ans+=a\[n\]\*2;
n--;
cnt++;
}
int l=1,r=n;
while(cnt<=k){
ans+=a\[l\]+a\[r\];
l+=w\[k\]-1;
k--;
r--;
}
cout<<ans<<'\\n';
}
return 0;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论