CF335F Buy One, Get One Free解题报告

解题报告

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

更好的阅读体验

题意

• 给定$n$个馅饼，每个价格为$a_i$。每买一个馅饼都可以赠送一个价格严格小于它的馅饼，求买到所有馅饼的最小花费。
• 数据范围：$1\leqslant n\leqslant 10^5$。

分析

反悔贪心。

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

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

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

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

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

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

• $s>k$时，我们把兑换$k$改成买$k$，并用兑换$k$的名额和$k$产生的名额兑换两个$s$一定比原来的决策更优，因此我们去掉$k$，然后把两个$s$放入数据结构中（当只剩下一个$s$时就只需要放一个就好了）。
• $s<k$时，我们可以保留$k$，也可以反悔$k$买两个$s$，我们保留$k$，并抽象出一个价格为$2s-k$的馅饼放入数据结构中，那么我们发现这可以包含所有的决策（当只剩下一个$s$时就不需要加入这个馅饼了，还有$2s-k<0$时也不能加入这个馅饼）：
• • 如果单选$2s-k$这个馅饼就是全价买$k$，把两个名额给$s$；
• • 如果单选$k$就是不改变决策；
• • 如果同时选择$k,2s-k$，那么就是用其他的名额选择两个$s$。

你可能直接用了个数组保存可以反悔的决策，然而你会在$\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;
}