C. RationalLee(贪心+思维)

Problem - 1369C - Codeforces

 

李的背包里有n个整数a1,a2,...,an，而他有k个朋友。李想在他的朋友之间分配他背包里的所有整数，这样，第i个朋友将得到正好是wi个整数，每个整数将被交给正好一个朋友。

让我们把一个朋友的幸福感定义为他将得到的最大和最小的整数之和。

李想让他的朋友尽可能地快乐，换句话说，他想让朋友的快乐之和最大化。现在他要求你计算出朋友幸福的最大总和。

输入
第一行包含一个整数t（1≤t≤104）--测试案例的数量。

接下来的3t行包含测试用例--每三行一个。

每个测试用例的第一行包含两个整数n和k（1≤n≤2⋅105；1≤k≤n）--李拥有的整数和李的朋友的数量。

每个测试案例的第二行包含n个整数a1,a2,...,an（-109≤ai≤109）--李拥有的整数。

第三行包含k个整数w1,w2,...,wk（1≤wi≤n；w1+w2+...+wk=n）--李想给每个朋友的整数数目。

保证测试案例的n之和小于或等于2⋅105。

输出
对于每个测试案例，打印一个单一的整数--Lee能够实现的最大幸福之和。

题解:
分两种情况讨论

1.假如一个朋友需要的整数为一,最大最小均为同一个数,应该给他最大的数

2.我们知道一个人的贡献只和最大值最小值有关，中间那些是什么并不关心，所以我们从拿的最多的那个人开始，因为当前剩下的数中，最小和最大的那两个数肯定是要被计算的，所以我们把这两个数给到这个人，中间的话我们考虑贪心，把剩下尽可能小的数尽可能给他，这样对这个的贡献是不影响的而且还能提高别人的贡献。

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int a[200050];
int b[200050];
void solve()
{
	int n,k;
	cin >> n >>k;
	for(int i = 1;i <= n;i++)
	cin >> a[i];
	sort(a+1,a+1+n,[](int x,int y){return x>y;});
	for(int i = 1;i <= k;i++)
	{
		cin >> b[i];
	}
	sort(b+1,b+1+k);
	long long ans = 0;
	int pos = k + 1;
	for(int i = 1;i <= k;i++)
	{
		if(b[i] == 1)
		{
			ans += (a[i]*2);
		}
		else
		{
			pos = i;
			break;
		}
	}
	int l = pos ,r = n;
	for(int i = k;i >= pos;i--)
	{
		ans += a[l]+a[r];
		l++;
		r -= b[i]-1;
	}
	cout<<ans<<"\n";
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}