阵容挑选

题目描述

Karl 与木宝在玩一款足球游戏，这款游戏中他们需要挑选一些球员来组成阵容。

初始时，Karl 和木宝各自有一个包含 $n$ 名球员的球员池，其中每名球员都有一个战力值。

Karl 和木宝轮流进行决策，Karl 抢先进行。每次决策他们都要从以下行动中选择一个进行：

• $1$. 从自己的球员池中选择一名球员，将他加入到自己的阵容当中。

• $2$. 从对方的球员池中选择一名球员，将他永久从对方的球员池中移除。

$2n$ 轮决策后，Karl 和木宝需要从他们所选的球员中再选择最多 $k$ 名球员（有可能不够 $k$ 名）组成最终阵容。

假设 Karl 的最终阵容中球员的战力值之和为 $s_a$，木宝的最终阵容中球员的战力值之和为 $s_b$，Karl 的目标是最大化 $s_a - s_b$，木宝的目标是最小化这个值。如果他们都采取最优策略，$s_a - s_b$ 的值会是多少？

输入格式

第一行一个整数 $n,k$ 表示各自能挑选的初始球员数量以及最多能选择 $k$ 名球员组成最终阵容。

第二行 $n$ 个整数 $a_i$，表示 Karl 的初始球员池中每名球员的战力。

第三行 $n$ 个整数 $b_i$，表示木宝的初始球员池中每名球员的战力。

输出格式

输出一行，一个整数，表示双方都采取最优策略下的答案。

样例 #1

样例输入 #1

2 1
3 6
2 4

样例输出 #1

2

样例 #2

样例输入 #2

4 1
1 3 5 7
2 4 6 8

样例输出 #2

0

样例 #3

样例输入 #3

3 2
1 9 11
3 7 8

样例输出 #3

4

提示

【数据范围】

• 对于 $100\%$ 的数据，$1 \le n \le 10^5,1 \le k \le 10,1 \le a_i,b_i \le 10^8$。

测试点编号	$n$	$k$
$1 \sim 6$	$n \le 10$	$k \le 10$
$7 \sim 12$	$n \le 10^5$	$k = 1$
$13 \sim 20$	$n \le 10^5$	$k \le 10$

#include<bits/stdc++.h>
using namespace std;
int ac[100005],bc[100005];
int main(){
	int n,k1,k2,ans=0;
	cin>>n>>k1;
	k2=k1;
	for(int i=0;i<n;i++){
		cin>>ac[i];
	}
	for(int i=0;i<n;i++){
		cin>>bc[i];
	}
	sort(ac,ac+n);
	sort(bc,bc+n);
	int acnt=n-1,bcnt=n-1;
	for(int i=0;i<2*n;i++){
		if(i%2==0){
			if(ac[acnt]>=bc[bcnt]&&k1!=0){
				ans+=ac[acnt--];
				k1--;
			}else{
				bcnt--;
			}
		}else{
			if(bc[bcnt]>=ac[acnt]&&k2!=0){
				ans-=bc[bcnt--];
				k2--;
			}else{
				acnt--;
			}
		}
	}
	cout<<ans;
	return 0;
}