洛谷 U138347 贩卖武器

洛谷传送门

题目背景

SeawaySeawa**y所效命的AlphaAlpha国和邪恶的EulerEuler国之间关系越来越紧张，空气中的火药味很浓。二国决定尽快买入足够的武器以防万一。军备竞赛始终是国力竞争的重要一环，AlphaAlpha国必然不会让自己在开战之前就陷入劣势。所以，AlphaAlpha国人民委员会任命SeawaySeawa**y为军工采购部部长，全面负责买入武器的工作......

题目描述

两国都有自己的武器供应商，而且两个武器供应商都有NN种武器可卖（两国所卖的武器不可能相同）。每种武器都有一个杀伤力k_ik**i。每次，每国可以在两种操作中选择一种：

第一种：在自己的供应商中选择一种武器买入。

第二种：在对方的供应商中选择一种武器摧毁。摧毁的意义是，这种武器既不可以被自己买入，也不可以被对手买入。

显然，如何选择这两种操作直接决定了两国武器质量的优劣。假设EulerEuler国的军工采购部部长和SeawaySeawa**y都很聪明，每次都会选择最优的操作。那么，请判断：AlphaAlpha国的武器质量（也就是所有买入武器的杀伤力之和）能否大于EulerEuler国的武器质量，并求出二者差值。

输入格式

从文件weapon.inweapo**n.i**n中读入数据。

第一行一个整数NN，接下来的两行，每行NN个整数，分别表示AlphaAlpha国，EulerEuler国的武器供应商所提供的每种武器的杀伤力k_ik**i。

输出格式

输出到文件weapon.outweapo**n.out中。

第一行为YESYES和NON**O，表示AlphaAlpha国的武器质量能否大于EulerEuler国的武器质量。第二行输出一个整数ansans，表示两者差值。

命题背景：

同样没啥背景。

题解：

看到”足够聪明“就开始想贪心。

贪心这个东西，就是直觉好的人一眼切，直觉不好的人反复错。

对于这道题，贪心策略非常好想也非常好证明。如果当前我方剩下的最大数要比对面剩下的最大数大，那对面怎么拿，我们都是赚的，所以这时取我方最大的。反之，我们怎么拿，只要对面把对面最大的拿走，我们都是亏的。所以贪心策略就出来了。

至于实时维护最大值，可以用堆来实现。

代码：

#include<cstdio>
#include<queue>
#define int long long
using namespace std;
int n,ansa,ansb;
priority_queue<int> q[3];
//q[1]:A q[0]:B
signed main()
{
	scanf("%I64d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%I64d",&x);
		q[1].push(x);
	}
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%I64d",&x);
		q[0].push(x);
	}
	q[1].push(-1);
	q[0].push(-1);
	int tot=n*2;
	for(int i=1;i<=tot;i++)
	{
		int a=q[1].top();
		int b=q[0].top();
		if(i&1)//a's turn
		{
			if(a<b)
				q[0].pop();
			else
			{
				q[1].pop();	
				ansa+=a;
			}
		}
		else//b's turn
		{
			if(b<a)
				q[1].pop();
			else
			{
				q[0].pop();
				ansb+=b;
			}
		}
	}
	printf("%I64d",ansa-ansb);
	return 0;
}