自动搬运

查看原文

来自洛谷，原作者为

	int_R 我在衡水上高三没空想你

搬运于2025-08-24 22:37:48，当前版本为作者最后更新于2022-08-25 11:22:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

贪心好题

P8298 [COCI2012-2013#2] POPUST

前记

蒟蒻第一篇题解

upd 2023.8.1 修缮细节

题目描述

Mirko 像熊一样饥饿，发现了一家当地餐馆。这家餐厅提供 $N$ 顿饭，并且有一个有趣的定价政策：每顿饭都有两个指定价格，$A_i$ 和 $B_i$。Mirko 点的第一道菜只需要付 $A$ 元，其他菜都需要付 $B$ 元。

Mirko 无法决定点多少菜。为了更简单地作出决定，他向你求助。对于任意 $k\in[1,N]$，点 $k$ 道菜最少要付的钱。Mirko 不在乎他点了哪些特别的饭菜，也不管他点菜的顺序，但他不会点两道同样的菜。

---

贪心思想

观察此样例

3
10 5
9 3
10 5

这道题的突破点在于：由题意得，我们并不关注点菜顺序，所以对于每个 $k\in[1,N]$，只需要取出 $1$ 个 $a_i$ 和 $k-1$ 个 $b_i$ 即可。

所以我们先按照 $b_i$ 排序。

9 3
10 5
10 5

排序后我们可以看出，由于 $b_i$ 为有序的，所以尽可能选取编号较小( $b_i$ 较小)的是较优的。取出前 $k-1$ 个 $b_i$，再在后 $n-k+1$ 取出一个 $a_i$。

$ans=(\sum\limits_{i=1}^{k-1} b_i) + (\min\limits_{i=k}^n a_i)$

但是我们发现，面对下面这个样例，这样就是错误的。

3
1 3
114514 7
1919810 9

按照上面的式子计算，当 $k=2$，$ans=3+114514=114517$，而明显可见，$ans=b_2+a_1=7+1=8$ 更为优。因为在第一个式子中我们选出的 $a$ 的编号是 $\geqslant k$ 的，然而在后面的 $a_i$ 值较大时，这样就不够优了。

这时我们要取出前 $k$ 个 $b_i$，再在前 $k-1$ 个中去掉一个 $b_i$，取出一个 $a_i$。

设取出 $a_j$。

$ans=(\sum\limits_{i=1}^k b_i) - b_j + a_j (j<k)$

贪心使 $a_j-b_j$ 最小。

得

$ans=(\sum\limits_{i=1}^k b_i) + (\min\limits_{i=1}^{k-1} a_i - b_i)$

综上所述，两种方案取较小值。

$\boxed{ ans=min( (\sum\limits_{i=1}^{k-1} b_i) + (\min\limits_{i=k}^n a_i),(\sum\limits_{i=1}^k b_i) + (\min\limits_{i=1}^{k-1} a_i - b_i) )}$

总结就是两种情况：

1.完完全全选择最小的 $b_i$ ——先选前 $k-1$ 个 $b_i$，然后在后 $n-k+1$ 取出一个 $a_i$；

2.选择一个较大的 $b_i$ 以换取一个较小的 $a_i$ ——取出前 $k$ 个 $b_i$，再在前 $k-1$ 个中去掉一个 $b_i$，取出一个 $a_i$。

---

代码实现

根据上面的式子，我们发现我们只需要维护三个东西

$b_i$ 的前缀和————很显然直接前缀和就行

$a_i$ 的最小值————从后往前预处理一遍，记录当前节点到最后的最小值

$a_i-b_i$ 的最小值————从前往后预处理，记录从最开始到当前节点的最小值

然后边更新边输出就好了，其实代码非常简单，而且也没什么可说的

#include<cstdio>
#include<algorithm>
#define int long long//要long long
using namespace std;
const int MAXN=5e5+10;
struct d{int a,b;}p[MAXN];//a[i]和b[i]
int n,pre[MAXN],MIN[MAXN],c[MAXN];//三个数组分别对应上面的三个
inline bool cmp(d x,d y){return x.b<y.b;}//以b[i]为关键字排序
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].a,&p[i].b);
	sort(p+1,p+1+n,cmp);MIN[n+1]=0x3f3f3f,c[0]=0x3f3f3f;//赋初值
	for(int i=1;i<=n;i++)//正着预处理
	{
		pre[i]=pre[i-1]+p[i].b;
		c[i]=min(c[i-1],p[i].a-p[i].b);
	}
	for(int i=n;i>=1;i--) MIN[i]=min(MIN[i+1],p[i].a);//反向预处理
	for(int i=1;i<=n;i++) printf("%lld\n",min(pre[i-1]+MIN[i],pre[i]+c[i-1]));//输出
	return 0;
}