Codeforces Round #652 (Div. 2) C. RationalLee

C. RationalLee

解题思路
$双指针+贪心$

• 我们先对数组$a[],b[]$排序，当$w_i=1$时，最大值等于最小值，所以我们要保证$w_i=1$时，拿剩下数中最大的
• 因为每个人获得的贡献是他拿的数的最大值+最小值，所以最大值和最小值中间的数是没有用的，我们就可以使这些没有用的数尽可能的小，这样才能保证贡献尽可能大，所以$w_i$越大，最小值需要越小
• 当$w_i>1$时，我们要拿剩下数中的最大的数以及w[i]-1个小数分给第$i$个人，从$k$到$1$，这样就能使之后个每人拿到的最小值尽可能大
• 具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int a[N],w[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
 
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		for(int i=0;i<n;i++)
			cin>>a[i];
		for(int i=0;i<k;i++)
			cin>>w[i];
		sort(a,a+n);
		sort(w,w+k);
		int l=0,j=0,r=n-1,ans=0;
		while(j<k){
			while(w[j]==1){
				ans+=a[r]*2;
				r--;
				j++;
			}
			if(j>=k) break;
			ans+=a[r]+a[l];
			l+=w[k-1]-1;
			r--;
			k--;
		}
		cout<<ans<<endl;
	} 
	return 0;
}