P8298 [COCI 2012/2013 #2] POPUST

题目背景

本题分值按 COCI 原题设置，满分 $120$。

题目描述

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

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

输入格式

第一行一个正整数 $N(2\le N\le 5\times 10^5)$，表示菜品数量。

接下来 $N$ 行，每行两个正整数 $A_i,B_i(1\le A_i,B_i\le 10^9)$，题目已经描述。

输出格式

输出包含 $N$ 行，第 $k$ 行表示点 $k$ 道互不相同的菜最少需要花多少钱。

输入输出样例 #1

输入 #1

3
10 5
9 3
10 5

输出 #1

9
13
18

输入输出样例 #2

输入 #2

2
100 1
1 100

输出 #2

1
2

输入输出样例 #3

输入 #3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

输出 #3

1000000000
2000000000
3000000000
4000000000
5000000000

说明/提示

样例#1 解释/说明

• $k=1$: Mirko 开始点第 $2$ 道菜，共花费 $A_2=9$ 元。

• $k=2$: Mirko 开始点第 $1$ 道菜，接着点第 $2$ 道菜，共花费 $A_1+B_2=13$ 元。

• $k=3$: Mirko 开始点第 $1$ 道菜，接着点第 $2,3$ 道菜，共花费 $A_1+B_2+B_3=18$ 元。

C++实现

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

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容