全国信息学奥林匹克联赛（NOIP2018）复赛 提高组 day1答案及解析.pdfVIP

一、实操题

1、铺设道路

【问题描述】

春春是一名道路工程师，负责铺设一条长度为n的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是n

块首尾相连的区域，一开始，第i块区域下陷的深度为di。

春春每天可以选择一段连续区间[L,R]

，填充这段区间中的每块区域，让其下陷深度减少

1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为0。

春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变

为0。

【输入格式】

输入文件名为road.in。

输入文件包含两行，第一行包含一个整数n，表示道路的长度。

第二行包含n个整数，相邻两数间用一个空格隔开，第i个整数为di。

【输出格式】

输出文件名为road.out。

输出文件仅包含一个整数，即最少需要多少天才能完成任务。

【输入输出样例1】

【样例解释】

一种可行的最佳方案是，依次选择：

[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。

【数据规模与约定】

对于30%的数据，1≤n≤10；

对于70%的数据，1≤n≤1000；

对于100%的数据，1≤n≤100000，0≤di≤10000。

参考答案：由于数据规模较大，我们需要寻找一种高效的算法来求解。观察到题目

中的限制条件，我们可以使用贪心算法来解决问题。我们可以将道路的下陷深度看

作是一堆堆石头，每天春春可以选择一段连续的区域，将这段区域的下陷深度减少

1，相当于将这段区域的石头搬走。为了最小化天数，我们可以选择下陷深度最大

的区域进行填充。我们可以维护一个下陷深度的数组，每次选择下陷深度最大的区

域进行填充，直到所有区域的下陷深度都为0。具体实现时，我们可以使用优先队

列（堆）来维护下陷深度的数组，每次取出下陷深度最大的区域进行填充。时间复

杂度为O(nlogn)，其中n为道路的长度。

解析：【喵呜刷题小喵解析】：

本题是一道典型的贪心算法问题。由于数据规模较大，暴力枚举所有可能的区间是

不现实的。因此，我们需要寻找一种高效的算法来求解。

观察题目中的限制条件，我们可以发现，每天春春可以选择一段连续的区域，将这

段区域的下陷深度减少1。这意味着我们可以将道路的下陷深度看作是一堆堆石头

，每次可以选择一堆石头进行搬运，直到所有石头都被搬走。

为了最小化天数，我们应该选择下陷深度最大的区域进行填充。因此，我们可以使

用优先队列（堆）来维护下陷深度的数组，每次取出下陷深度最大的区域进行填充

。

具体实现时，我们可以先将所有区域的下陷深度放入优先队列中，然后每次取出下

陷深度最大的区域进行填充，直到所有区域的下陷深度都为0。由于优先队列的时

间复杂度为O(logn)，因此总时间复杂度为O(nlogn)，其中n为道路的长度。

由于题目中要求输出最少需要多少天才能完成任务，因此我们需要记录填充的天数

。每次取出下陷深度最大的区域进行填充时，天数加1。最后输出天数即可。

需要注意的是，题目中要求在选择区间时，需要保证区间内的每块区域在填充前下

陷深度均不为0。因此，在每次取出下陷深度最大的区域进行填充前，我们需要检

查该区域的下陷深度是否不为0。如果为0，则无法填充，需要跳过该区域。

2、货币系统

【问题描述】

在网友的国度中共有n种不同面额的货币，第i种货币的面额为

a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为

n、面额数组为a[1..n]的货币系统记作(n,a)。

在一个完善的货币系统中，每一个非负整数的金额x

都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i]满足a[i]×

t[i]的和为

x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x

不能被该货币系统表示出。例如在货币系统n=3,a=[2,5,9]中，金额1,3

就无法被表示出来。

两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数

x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b)，满足(m,b)

与原来的货币系统(n,a)等价，且m

尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的m。

【输入格式】