[COCI2012-2013#2] POPUST 题解

题意

有 \(N \thinspace (2 \leq N \leq 5 \times 10^5)\) 个物品，每个物品的原价是 \(b_i\) 元。每次选物品时，第一件选出的物品 \(i\) 价格变为 \(a_i\) 元，问选 \(i \thinspace (1 \leq i \leq N)\) 个互不相同的物品最少需要多少钱。

思路

错误思路

很容易就可以想出一种贪心。

先对每个物品的价格按照 \(b_i\) 从小到大排序。

在选择拿出 \(i\) 个物品时，先选出前 \(i-1\) 个物品按照价格 \(b\) 作为之后购买的物品，再在 \(i \sim N\) 个物品中选择价格 \(a\) 最小的物品作为第一个购买的物品。

此时答案即为 \(\sum \limits_{j=1}^{i-1} b_j + \min \{ a_i,a_{i+1},a_{i+2},\cdots,a_N \}\)。

求和时可用前缀和优化时间，取最小值时可统计后缀最小值优化时间。

正确思路

很显然可以发现，只选择上述贪心策略是不对的。

除了可以在 \(i \sim N\) 个物品中选择价格 \(a\) 最小的物品作为第一个购买的物品外，还可以在 \(1 \sim i\) 个物品中选择价格 \(a\) 与价格 \(b\) 差值最小的物品，将其变为第一个购买的物品。

此时答案即为 \(\sum \limits_{j=1}^{i} b_j + \min \{ a_1-b_1,a_2-b_2,a_3-b_3,\cdots,a_i-b_i \}\)。

求和时依然可用前缀和优化时间，取最小值时可用前缀最小值进行优化。

将两种综合起来取最小值，就是最终的答案。

注意： 由于 \(1 \leq a_i,b_i \leq 10^9\),所以数据类型要选择 long long。

代码

#include<stdio.h>
#include<algorithm>
typedef long long ll;
const int N=5e5+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct node{
	ll x,y;
	bool operator < (const node &a) const{return y<a.y;}
}a[N];
int n;
ll minn[N],minx[N];
int main(){
	scanf("%d",&n);
	ll ans=inf;
	for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y),ans=std::min(ans,a[i].x);
	printf("%lld\n",ans);//选择1个物品的答案 
	std::sort(a+1,a+n+1);
	minx[n+1]=inf;
	for(int i=n;i;i--) minx[i]=std::min(minx[i+1],a[i].x);//统计后缀最小值 
	minn[1]=a[1].x-a[1].y;
	ans=a[1].y;
	ll ans1=0;
	for(int i=2;i<=n;i++){
		minn[i]=std::min(minn[i-1],a[i].x-a[i].y);//统计前缀最小值 
		ans+=a[i].y;//情况2前缀和 
		ans1+=a[i-1].y;//情况1前缀和 
		printf("%lld\n",std::min(ans+minn[i],ans1+minx[i]));//最终答案 
	}
	return 0;
}