C/C++教程

【CF335F】 Buy One, Get One Free(反悔贪心)

本文主要是介绍【CF335F】 Buy One, Get One Free(反悔贪心),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题链接

题意

有 \(n\) 个物品,你每购买一个物品可以免费获得一个价格严格小于它的物品,求得到所有物品的最小代价。

数据范围

\(1 \leq n \leq 5 \times 10^5\)

思路

考虑贪心,最朴素的想法就是从大到小枚举物品,并且免费获得第一个价格严格小于它的物品。但很显然这样的想法是错误的,原因在于拿走最大的可以免费的物品,可能会导致后面浪费了一次免费的机会,此时有可能买下这个物品更优,可以考虑反悔贪心。

可以用一个小根堆维护当前所免费的物品,考虑当前有两个价值为 \(x\) 的物品,可以做以下两种选择:

1.两个物品都直接购买,代价为 \(2x\)。

2.对于之前的物品,有一个策略是买了 \(a\) 免费 \(b\)(此时满足 \(a>b>x\)),此时将这个决策反悔,即买 \(a\) 和 \(b\),免费 \(2x\)。此时的就相当于多买了一个 \(b\)。代价为 \(b\)。

若 \(2x \leq b\),那么直接购买 \(2x\) 更优;

若 \(2x > b\),那么就可以考虑将之前的决策反悔。

对于反悔操作,可以发现实际上减少的代价为 \(2x-b\)。那么就可以直接把这个 \(2x-b\) 看成一个免费的物品丢到小根堆中。表示此时又可以反悔操作 \(2\)。而 \(2x-b\) 反悔后,自然又可以反悔一次买 \(a\) 免费 \(b\) 的操作。而由于 \(x<b\),自然有 \(2x-b<b\),那么在小根堆里自然先会反悔 \(2x-b\) 再反悔 \(b\)。直接把 \(b\) 也丢入小根堆中即可。

如果当前枚举到的 \(x\) 的价值大于堆顶元素,那么显然反悔堆顶的决策,转而免费这两个(如果只剩下一个 \(x\) 就只免费这一个)物品会更优,直接将两个 \(x\) 丢入堆中即可。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5e5+10;
#define LL long long
priority_queue<int,vector<int>,greater<int> >q;
int a[N],b[N],n,m,cnt[N],num[N];
LL ans;
int main()
{
	scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),ans+=a[i];
	sort(a+1,a+n+1);reverse(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		if(i==1||a[i]!=a[i-1]) num[++m]=a[i];
		cnt[m]++;
	}
	int c1=0,c2=0,p=0;
	for(int i=1;i<=m;i++)
	{
		p=min(c1-2*(int)q.size(),cnt[i]);c2=0;
		for(int j=1;j<=p;j++) b[++c2]=num[i];
		p=min(c1,cnt[i])-p;//p为当前最多可以免费的数量 
		for(int j=1;j<=p;j+=2)
		{
			int x=q.top();
			if(x<num[i])
			{
				b[++c2]=num[i];
				if(j<p) b[++c2]=num[i];
			}
			else
			{
				b[++c2]=x;//b
				int y=2*num[i]-x;
				if(j<p&&y>0) b[++c2]=y;//2x-b>0
			}
			q.pop();
		}
		for(int j=1;j<=c2;j++) q.push(b[j]);
		c1+=cnt[i];
	}
	while(!q.empty()) ans-=q.top(),q.pop();
    printf("%lld\n",ans);
 	return 0;
}
这篇关于【CF335F】 Buy One, Get One Free(反悔贪心)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!