自动搬运

查看原文

来自洛谷，原作者为

	Phoenix_chaser 昔人已乘 int 去 此地空余 long long 人

搬运于2025-08-24 22:21:38，当前版本为作者最后更新于2020-09-15 21:10:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

排序+去掉每三个中最小的

本题核心：让优惠最大化。

既然要价格最小，那就要让优惠最大。

本题的优惠是让三个中 最小的那个不付钱 ，所以我们要去让每组三个数中的 最小的尽量大 ，这样的优惠的价格是最多的。

举个例子

9

8 9 7 5 6 4 8 5 4

首先要进行排序，这里的排序要 降序排列 ，让大的值在前面。从前往后数，每三个为一组，这样的从前往后每一次优惠都是当前可以进行优惠的 最大值。

排序后： 9 8 8 7 6 5 5 4 4

第一次优惠后：

9 8 0 7 6 5 5 4 4

第二次优惠后:

9 8 0 7 6 0 5 4 4

第三次优惠后：

9 8 0 7 6 0 5 4 0

优惠完毕，将所有加起来。

还有一点：

这种优惠在一次性购买1或2本书时，不存在。但这里不需要特殊处理，因为我是从第三个数开始处理的，只有1或2本书时并没有进行处理。详细看代码。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[100003],ans=0;
int cmp(int a,int b){
	return a>b;
	//将sort变成降序排列 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+n+1,cmp);
	//排序 
	for(int i=3;i<=n;i=i+3) a[i]=0;
	//核心：降序排列，所以每组第三个为每组最小 
	for(int i=1;i<=n;i++)  ans=ans+a[i];
	//将优惠过的值加起来，被优惠过的都变成了0 
	cout<<ans;
	return 0;
}

感谢观看

The End