欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

卡牌游戏 IV

程序员文章站 2022-06-24 11:53:36
B - 卡牌游戏 IV蒜头君在玩一种卡牌游戏,他有 n 张卡牌,每张卡牌上写着两个正整数 ai,bi ,ai 表示这张卡牌的能量值,bi表示这张卡牌的魔法值。他准备一张一张打出这 n张卡牌,每张卡牌会对敌人造成的伤害是这张卡牌的能量值乘魔法值。但是蒜头君觉得这样把这 n张卡牌都出完对敌人造成的伤害之和还是不够大,所以他偷偷学会了一种仙术。蒜头君施展一次仙术的时候会任意选择两张卡牌,把它们的魔法值交换,能量值不交换。蒜头君可以使用任意次仙术,当然也可以一次都不使用,他想知道使用了若干次仙术以后一张一张打...

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

3
1 6
3 4
5 2

Sample Output

44

注意题目给的要求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;
 } 

本文地址:https://blog.csdn.net/weixin_50829127/article/details/110177845

相关标签: c++ c语言