首页 > 代码库 > UVa 11369 - Shopaholic

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