CF335F 思维难题题解

きりと · 2021-07-12 21:11:48 · 题解

题目传送门

题目大意

现有 n 件物品，每件物品有其价格 a_i ，购买一个物品后可以白嫖一件价格更低的物品，试求购买所有物品的最小代价。

解题思路

部分思路参考这篇题解，但由于这篇题解讲的不是很到位，于是想再作一些补充，并提供一种较为清晰，循序渐进的解题思路。

先将所有物品按价格从大到小排序，对于每件物品，考虑它是否要白嫖，然后发现对一件物品白嫖与否只与其价值大小有关，所有可以将价值相同的物品分入一组，按组考虑。

对于第 i 组数量为 c_i 的物品，先考虑能白嫖就白嫖，我们可以开一个临时栈 d 用来记录对当前这组物品进行决策时，决定要白嫖的物品的价值（原因之后解释）。

一开始可以无脑白嫖的数量是 \min( 比这组物品价值大的物品的数量 - 之前白嫖的物品数量 \times 2，c_i )，直接暴力加入栈内。（此处要乘 2 的原因是：白嫖一次对应着花一次钱，所以此时计算剩余未买物品就要乘 2 了）

然后考虑剩下的 p 件物品。我们假设当前为止，白嫖的物品里价格最小的物品的价格为 x。由于我们进行了排序，所以可以保证 x>a_i 。如果我们将 x 买下，然后来白嫖 a_i，那就可以相较于买下 a_i ，净赚 2\times a_i。所以，当 2\times a_i>x 时，我们可以考虑直接不白嫖 x ，而是白嫖 a_i，可以用小根堆维护 x，此时，之前的 d 的作用就凸显出来了，d 的存在使得新白嫖的物品不会影响当前这组的决策，也就是不存在广义上的自己嫖自己的情况。（

此时问题就转变成了，我们怎么对堆顶物品进行“撤销”操作了。原先，我们是买了某件价格为 y （y>x）的物品，然后嫖了堆顶物品，这导致我们又少赚了 2\times a_i，所以它产生的代价是：y+2\times a_i，而现在我们买了堆顶物品，产生的代价是 y+x ，所以应该赚了 2\times a_i-x ，我们可以把它看做一件物品，丢到堆里面，最终可以实现一环扣一环地撤销，决策。

最后堆里面留下的物品的价值之和就是可以白嫖的钱辣！

感觉这题的难点其实在理解两个式子中的 \times 2 上，因为白嫖少花的钱 \neq 当前决策赚的钱，这和生活常识其实是相违背的，因为生活中我们没有绝对必需品，而题中的每一个物品都是必须的。

Code

#include<bits/stdc++.h>
#define int long long
#define forr(i,l,r) for(register int i=l;i<=r;i++)
#define ffor(i,r,l) for(register int i=r;i>=l;i--)
using namespace std;
const int N=5e5+10;
int a[N],b[N],c[N],d[N];
priority_queue<int,vector<int>,greater<int> > q;
bool cmp(int q,int p)
{
    return q>p;
}
signed main()
{
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    int ans=0,c1=0;
    forr(i,1,n)
    {
        cin>>a[i];
        ans+=a[i];
    }
    sort(a+1,a+n+1,cmp);
    forr(i,1,n)
    {
        if(i==1||a[i]!=a[i-1])
        {
            b[++c1]=a[i];
        }
        c[c1]++;
    }
    int p=0,c2=0,c3=0,x,y;
    forr(i,1,c1)
    {
        c3=0;
        p=min(c2-2*(int)q.size(),c[i]);
        forr(j,1,p)
        {
            d[++c3]=b[i];
        }
        p=min(c2,c[i])-p;
        forr(j,1,p)
        {
            x=q.top();
            if(x<b[i])
            {
                d[++c3]=b[i];
                if(p>j)
                {
                    d[++c3]=b[i];
                }
            }
            else
            {
                d[++c3]=x;
                y=2*b[i]-x;
                if(j<p&&y>0)
                {
                    d[++c3]=y;
                }
            }
            q.pop();
            j++;
        }
        forr(j,1,c3)
        {
            q.push(d[j]);
        }
        c2+=c[i];
    }
    while(!q.empty())
    {
        ans-=q.top();
        q.pop();
    }
    cout<<ans<<endl;
    return 0;
}

最后能不能不要脸地讨个赞啊

CF335F 思维难题 题解

题目大意

解题思路

Code

CF335F 思维难题题解