当前位置：首页 > news >正文

B4156 [厦门小学生 C++ 2023] 太空旅行

news 2026/5/12 13:48:44

题目描述

在未来，太空旅行已经是一件稀松平常的事，星际部又宣称即将开通一条火星至天王星的航线。

所有的星际飞船必须先经过航线1 11（地球→ \to→火星），再经过航线X XX（火星→ \to→天王星）才能顺利抵达天王星。

为了避免星际飞船发生碰撞，每条航线只能有一架飞船正在行驶。已知星际飞船从地球到火星需要U ( i ) U(i)U(i)时间，火星到天王星需要V ( i ) V(i)V(i)时间。飞船们可能会滞留在火星，它们必须等待航线状态为空才能起飞。飞船到达火星和离开火星的顺序可能会不一致。

请计算从地球出发的N NN架星际飞船，全部抵达天王星，需要花费的最短时间。

输入格式

第1 11行：一个整数N NN，表示星际飞船的数量。

第2 22到N + 1 N+1N+1行：第i + 1 i+1i+1行包含两个空格隔开的整数：U ( i ) U(i)U(i)和V ( i ) V(i)V(i)。

输出格式

输出1 11行，一个单独的整数，表示所有飞船抵达天王星需要的最短时间。

输入输出样例 #1

输入 #1

3 6 4 8 1 2 3

输出 #1

说明/提示

样例解释

最优方案总耗时为：2 + 6 + 8 + 1 = 17 2+6+8+1=172+6+8+1=17。

飞船状态\时间	地球→ \to→火星出发时刻	地球→ \to→火星到达时刻	火星→ \to→天王星出发时刻	火星→ \to→天王星到达时刻
第 1 架	2 22	8 88	8 88	12 1212
第 2 架	8 88	16 1616	16 1616	17 1717
第 3 架	0 00	2 22	2 22	5 55

第3 33架飞船最先从地球出发抵达火星，然后到天王星。第3 33架飞船抵达火星后，第1 11架飞船即刻从地球出发。等第1 11架飞船抵达火星后，第2 22架飞船最后从地球出发。

【数据范围】

对于所有数据有：1 ≤ N ≤ 25000 1 \leq N \leq 250001≤N≤25000，1 ≤ U ( i ) , V ( i ) ≤ 50000 1 \leq U(i),V(i) \leq 500001≤U(i),V(i)≤50000。

测试点编号	特殊性质	1 ≤ N ≤ 1 \leq N \leq1≤N≤	1 ≤ U ( i ) , V ( i ) ≤ 1 \leq U(i),V(i) \leq1≤U(i),V(i)≤
1 ∼ 2 1\sim 21∼2	无	10 1010	100 100100
3 ∼ 8 3\sim 83∼8	无	100 100100	500 500500
9 ∼ 12 9\sim 129∼12	无	10000 1000010000	5000 50005000
13 ∼ 14 13\sim 1413∼14	B	25000 2500025000	50000 5000050000
15 ∼ 16 15\sim 1615∼16	A	25000 2500025000	50000 5000050000
17 ∼ 20 17\sim 2017∼20	无	25000 2500025000	50000 5000050000

其中：

特殊性质 A：保证所有的U ( i ) U(i)U(i)都相同。
特殊性质 B：保证所有的V ( i ) V(i)V(i)都相同。

思路

考虑贪心算法，此题就是因为证明难度大才评为紫题，作者比较菜，所以不会证，但代码较简单。

代码

#include<bits/stdc++.h>usingnamespacestd;intn;structdid{inta,b;}p[30001];boolcmp(did x,did y){if(x.a<x.b){if(y.a<y.b)returnx.a<y.a;return1;}else{if(y.a<y.b)return0;returnx.b>y.b;}}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>p[i].a>>p[i].b;sort(p+1,p+1+n,cmp);intA=0,B=0;for(inti=1;i<=n;i++){A+=p[i].a;if(B<A)B=A;B+=p[i].b;}cout<<B<<endl;return0;}