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

一、实操题

1、积木大赛

【题目描述】

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的

大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要hi。

在搭建开始之前，没有任何积木（可以看成n块高度为0

的积木）。接下来每次操作，小朋友们可以选择一段连续区间[L,R]，然后将第L块

到第R块之间（含第L块和第R块）所有积木的高度分别增加1。

小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作

次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出

最少的操作次数。

【输入】

输入文件为block.in

输入包含两行，第一行包含一个整数n，表示大厦的宽度。

第二行包含n个整数，第i个整数为hi。

【输出】

输出文件为block.out

仅一行，即建造所需的最少操作数。

【输入输出样例】

【样例解释】

其中一种可行的最佳方案，依次选择[1,5][1,3][2,3][3,3][5,5]

【数据范围】

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

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

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

参考答案：对于每个高度hi，我们需要找到一个前缀和si，使得si-1=hi

si。这样，我们可以将高度hi的积木高度增加si-

hi，使得积木高度达到si。我们可以使用单调栈来维护前缀和si。对于每个高度hi，

我们在栈中找到第一个小于等于hi的前缀和s，那么我们需要将第s+1块到第i块积木

的高度都增加hi-

s。我们可以维护一个变量res，表示操作次数。对于每个高度hi，我们更新res为res

和hi-s中的较大值。最后，我们输出res即可。

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

这道题目要求我们找到一种最优策略，使得将宽度为n的大厦搭建成指定的高度所

需的操作次数最少。我们可以观察到，如果我们将某段连续的积木高度都增加相同

的值，那么我们可以将这段积木看作是一个整体，它们的相对高度关系不会改变。

因此，我们可以将问题转化为寻找一种最优的分配方式，使得每次操作都能将尽可

能多的积木高度增加到目标高度。我们可以使用前缀和数组来记录每个位置之前所

有积木的高度和，然后对于每个高度hi，我们需要在前缀和数组中找到一个前缀和

s，使得s-1=his。这样，我们可以将高度hi的积木高度增加s-

hi，使得积木高度达到s。

我们可以使用单调栈来维护前缀和数组。对于每个高度hi，我们在栈中找到第一个

小于等于hi的前缀和s，那么我们需要将第s+1块到第i块积木的高度都增加hi-

s。我们可以维护一个变量res，表示操作次数。对于每个高度hi，我们更新res为res

和hi-s中的较大值。

最后，我们输出res即可。这种策略可以保证每次操作都能将尽可能多的积木高度

增加到目标高度，从而得到最优解。

2、花匠

【问题描述】

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋

决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，

同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数h1,h2,…,

hn。设当一部分花被移走后，剩下的花的高度依次为g1,g2,…,

gm，则栋栋希望下面两个条件中至少有一个满足：

条件A：对于所有的i，g2ig2i−1，且g2ig2i+1；

条件B：对于所有的i，g2ig2i−1，且g2ig2i+1。

注意上面两个条件在m=1时同时满足，当m1时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

【输入】

输入文件为flower.in。

输入的第一行包含一个整数n，表示开始时花的株数。

第二行包含n个整数，依次为h1,h2,…,hn，表示每株花的高度。

【输出】

输出文件为flower.out。

输出一行，包含一个整数m，表示最多能留在原地的花的株数。

【输入输出样例】

【输入输出样例说明】

有多种方法可以正好保留3株花，例如，留下第1、4、5株，高度分别为

5、1、2，满足条件B。

【数据范围】

对