UVa 11369 - Shopaholic

题目：商店打折，每买三件商品中最便宜的不要钱，问最多省多少钱。

分析：贪心。

            如果只有3个商品的话，那一定是最便宜的钱省下来；

            如果有6个商品的话，在省下最便宜的基础上，最好情况可以省下第3贵的商品的钱；

            由上述的推到过程可得贪心方法：

            将数据按从大到小排序，每次取前三个商品，可以省下其中最便宜的，此时最省钱；

            证明如下：

            定理：设有a > b > c > d > e > f，六个数字，分成两组，最小值和最大为 c + f；

            证明：含有 f 的3个数中的最小值一定是 f，那另一组最大的最小值为 c；得证；

            现在这里有n个数字，每3个分成一组，如果上述方法不对，则存在交换一对数能到更优解；

            这与上述定理矛盾；所以结论成立。

说明：冲进前1000了(⊙_⊙)。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int p[20004];

int cmp(int a, int b)
{
	return a > b;
}

int main()
{
	int t,n;
	while (~scanf("%d",&t))
	while (t --) {
		scanf("%d",&n);
		for (int i = 0 ; i < n ; ++ i)
			scanf("%d",&p[i]);
		
		sort(p, p+n, cmp);
		int sum = 0;
		for (int i = 2 ; i < n ; i+= 3)
			sum += p[i];
		
		printf("%d\n",sum);
	}
	return 0;
}

UVa 11369 - Shopaholic

原文：http://blog.csdn.net/mobius_strip/article/details/39076699