卡牌游戏 IV

作者: 街角_哭泣-
来源: 51数据库
2021-09-05

B - 卡牌游戏 IV

蒜头君在玩一种卡牌游戏，他有 n 张卡牌，每张卡牌上写着两个正整数 ai,bi ，ai 表示这张卡牌的能量值，bi表示这张卡牌的魔法值。

他准备一张一张打出这 n张卡牌，每张卡牌会对敌人造成的伤害是这张卡牌的能量值乘魔法值。但是蒜头君觉得这样把这 n张卡牌都出完对敌人造成的伤害之和还是不够大，所以他偷偷学会了一种仙术。

蒜头君施展一次仙术的时候会任意选择两张卡牌，把它们的魔法值交换，能量值不交换。蒜头君可以使用任意次仙术，当然也可以一次都不使用，他想知道使用了若干次仙术以后一张一张打出这 n张卡牌，对敌人造成的伤害之和最大是多少。

输入格式

第一行，一个正整数 n(1≤n≤105)。

接下来 n行，每行两个正整数 ai,bi(1≤ai,bi≤106)

输出格式

输出一行，包含一个整数，表示蒜头君使用若干次仙术以后一张一张打出卡牌，对敌人造成的伤害之和的最大值。

数据范围

对于 70%的数据，1≤n≤10的3次方,1≤ai,bi≤10的3次方

对于 100%的数据，1≤n≤10的5次方,1≤ai,bi≤10的6次方

Sample Input

Sample Output

注意题目给的要求10的6次方，所以我用了long long int，然后这题的题意理解一下大概就是当成一棵哈夫曼树求最大权值。就魔法值最大的和能量值最大的相乘，排下去就是最大值了。最后附上代码。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	cin>>n;
	long long int a[n],b[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i];
	}
	sort(a,a+n),sort(b,b+n);
	long long int sum=0;
	for(int i=0;i<n;i++)
	{
		sum+=a[i]*b[i];
	}
	cout<<sum<<endl;
	return 0;
 }