题解 | #玩具#

省流：B 玩具 题解

整体思路

整个题目属于贪心算法，整体思路就是从小到大排序然后从后面开始两个两个的买只买两者中最贵的那个，所以我们可以先排序在做处理，先从大到小排序排序后在从后面开始先取最大的然后跳过一个再取下面另一个，以此类推。

注意事项

一定要注意变量和数组的类型，不然会溢出导致不能 AC 定义的数组和 n 以及最后输出的答案类型都是 long long 。

代码部分

#include<iostream>
#include<algorithm>

using namespace std;
// 开数组范围
const int maxn = 1e6 + 9;

//根据题意开出long long int 型的数组
long long int a[maxn];

int main()
{
	long long int n, sum = 0;
	scanf("%lld", &n);
	
	for (long long int i = 1; i <= n; i ++ )
		scanf("%lld", &a[i]);
	// 对数组进行排序
	sort(a + 1, a + 1 + n);
	// 从后往前取，两个两个取，只把大的那个算入结果内
	for (long long int j = n; j >= 1; j -- ) 
	{
		sum += a[j];
		j --; // 略过下一个
	}
	
	printf("%lld\n", sum);
	
	return 0;
}