题解 P6530 【[COCI2015-2016#1] AKCIJA】

Phoenix_chaser · 2020-09-15 21:10:03 · 题解

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

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

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

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

举个例子

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;
}