2018年NOIP信息学奥赛提高组复赛C++真题day1

全国信息学奥林匹克联赛（ NOIP2018）复赛 提高组 day1 第1页共7页 CCF全国信息学奥林匹克联赛 （NOIP2018）复赛 提高组 day1 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 铺设道路 货币系统 赛道修建 英文题目与子目录名 road money track 可执行文件名 road money track 输入文件名 road.in money.in track.in 输出文件名 road.out money.out track.out 每个测试点时限 1s 1s 1s 测试点数目 10 20 20 每个测试点分值 10 5 5 附加样例文件 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 运行内存上限 512M 512M 512M 二．提交源程序文件名 对于C++语言 road.cpp money.cpp track.cpp 对于C语言 road.c money.c track.c 对于pascal语言 road.pas money.pas track.pas 三．编译命令（不包含任何优化开关） 对于C++语言 g++ -o road road.cpp -lm g++ -o money money.cpp -lm g++ -o track track.cpp -lm 对于C语言 gcc -o road road.c -lm gcc -o money money.c -lm gcc -o track track.c -lm 对于pascal语言 fpc road.pas fpc money.pas fpc track.pas 注意事项： 1、文件名（程序名和输入输出文件名） 必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为： Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内存 32GB。上述时限以此配置为准。 4、只提供 Linux格式附加样例文件。 5、特别提醒： 评测在当前最新公布的 NOI Linux下进行，各语言的编译器版本以其为准 。 全国信息学奥林匹克联赛（ NOIP2018）复赛 提高组 day1 第2页共7页 1．铺设道路 (road.cpp/c/pas) 【问题描述】 春春是一名道路工程师， 负责铺设一条 长度为 n 的道路。 铺设道路的主要工作是 填平下陷的地表。整段道路可以看作 是 n 块首尾相连的区 域，一开始， 第 i 块区域下陷的深度 为 d i 。 春春每天可以选择一段连续区间 [L,R] ，填充这段区间中的每块区域， 让其下陷深 度减少1。在选择区间时，需要保证，区间内的每块区域 在填充前下陷深度均不为 0 。 春春希望你能帮他 设计一种方案，可以在最短的时间内将 整段道路的下陷深度都变 为 0 。 【输入格式】 输入文件名为 road.in。 输入文件包含两行，第一行包含一个整数 n，表示道路的长度 。 第二行