首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。