题解 CF335F 【Buy One, Get One Free】

· · 题解

CF335F Buy One, Get One Free解题报告：

更好的阅读体验

题意

分析

反悔贪心。

我们考虑选择若干个馅饼使得它们免费，答案为所有馅饼的总价减去免费的馅饼的价格之和。

首先把价格相同的馅饼合并，然后把馅饼按价格从大到小排序，那么现在每一次赠送都只能依赖前面买过的馅饼。

我们设之前有k个馅饼是免费得到的，之前总共得到了sum个馅饼，现在的馅饼价格为s，有c个，那么就有sum-2k个馅饼是全价买的。

我们考虑先贪心地把前面全部的全价购买的馅饼兑换完，也就是先得到\min\{sum-2k,c\}个馅饼，那么还剩rst=c-\min\{sum-2k,c\}个馅饼。

我们考虑把之前的所有兑换操作都保存在一个数据结构里，那么我们可以对于里面的某些馅饼进行反悔，并重新选择当前的馅饼。

我们考虑之前免费得到的某个价格为k的馅饼，我们对k的大小讨论（你可能想问s<k不是很显然吗，但是由于在后文中我们加入的馅饼价格会有变化，因此并不满足s<k，这里需要讨论）：

你可能直接用了个数组保存可以反悔的决策，然而你会在\text{Test#6}挂掉：

7
10 9 5 5 4 3 2

你选取了10，然后兑换9，然后遇到两个5，抽象出一个价格为1的馅饼加入，然后遇到4，能反悔的第一个决策价格为9因此没有反悔但因为\text{pop}把9放到了后面，，遇到3直接兑换，而遇到2而当前反悔的决策为1也可以直接兑换。因此所有反悔的馅饼只包含9,3,2，花费为24。

实际上我们选取10,5,5,2花费为22更少，这告诉我们每次反悔的时候需要优先选取价值更小的决策，我们可以选取一个优先队列来保存决策就可以AC。

时间复杂度：我们考虑每次枚举堆内的馅饼都会把某个决策\text{pop}掉，而在\text{while}中每个馅饼也只能提供一次入堆的机会，因此复杂度为O(n\log n)。

代码

注意，这里的小根堆用权值取负实现。

#include<stdio.h>
#include<algorithm>
#include<queue>
#define int long long
using namespace std; 
const int maxn=500005;
int n,ans,tot,sum;
int a[maxn],s[maxn],c[maxn],tmp[maxn];
priority_queue<int>q;
inline int cmp(int a,int b){
    return a>b;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]),ans+=a[i];
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(i==1||a[i]!=a[i-1])
            s[++tot]=a[i],c[tot]++;
        else c[tot]++;
    }
    for(int i=1;i<=tot;i++){
        int ok=min(sum-(int)q.size()*2,c[i]),tmps=0,rst=min(c[i]-ok,sum-ok);
        for(int j=1;j<=ok;j++)
            tmp[++tmps]=s[i];
        for(int j=1;j<=rst;j+=2){
            int k=-q.top();
            q.pop();
            if(k<s[i]){
                tmp[++tmps]=s[i];
                if(j<rst)
                    tmp[++tmps]=s[i];
            }
            else{
                tmp[++tmps]=k;
                if(j<rst)
                    tmp[++tmps]=2*s[i]-k;
            }
        }
        for(int j=1;j<=tmps;j++)
            if(tmp[j]>=0) 
                q.push(-tmp[j]);
        sum+=c[i];
    }
    while(!q.empty())
        ans+=q.top(),q.pop();
    printf("%lld\n",ans);
    return 0;
}