[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;
}