NOIP2018T1 铺设道路
大约 3 分钟贪心
NOIP2018T1 铺设道路
【算法标签】 贪心
【语法标签】 :cin/cout、for循环、数组
春春要填平一条长度为 的道路,第 块区域的初始下陷深度为 。
每天可以选择一段连续的、每块深度均大于 0 的区间 ,将区间内所有区域深度减 。
求最少需要多少天,才能将所有区域深度变为 。
数据范围: ,。
二、解题思路
从简单情况入手
先看一个例子:d = [4, 3, 2, 5, 3, 5]。
如果只有第 1 块区域,深度为 4,显然需要填 4 天。
加入第 2 块区域(深度 3)后:
- 前 3 天可以同时填 ,把两块都填 3 次
- 第 1 块还多 1,再单独填 1 天
所以不一定每块都从零开始填。如果当前块比前一块矮,它可以"蹭"前一块的填充次数;如果比前一块高,多出来的部分必须额外填。
核心结论
从第 1 块开始,依次处理每一块:
- 如果 ,说明深度"上涨"了,多出来的部分 需要新增操作来填
- 如果 ,说明当前块可以沿用之前的操作,不需新增
因此答案为:
或者写成:
手动模拟
以样例 4 3 2 5 3 5 为例:
| 累计 | ||||
|---|---|---|---|---|
| 1 | 4 | 0 | 4 | 4 |
| 2 | 3 | 4 | 0 | 4 |
| 3 | 2 | 3 | 0 | 4 |
| 4 | 5 | 2 | 3 | 7 |
| 5 | 3 | 5 | 0 | 7 |
| 6 | 5 | 3 | 2 | 9 |
答案为 ,与题目样例一致。
为什么这是最优的?
每一次"上涨"都必须用新的操作来覆盖——因为之前填浅层区间的操作,到了这个位置深度已经"耗尽"了。把每次上涨的量累加起来,就是最少操作次数。
直观理解: 把深度数组画成柱状图,答案就是所有"上升台阶"的高度之和。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int d[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (d[i] > d[i - 1]) {
ans += d[i] - d[i - 1];
}
}
cout << ans << endl;
return 0;
}代码说明:
d[0]未显式赋值,全局数组默认初始化为 ,恰好满足 的要求- 只需一趟遍历, 即可求出答案
四、复杂度分析
- 时间复杂度: ,仅需一次线性扫描
- 空间复杂度: ,存储深度数组(若使用滚动变量可优化到 )
五、知识扩展
同类问题
这道题的思路与以下问题相通:
- 积木大赛(NOIP 2013 提高组):几乎完全相同的题目,只是描述不同
- USACO 上的类似问题:填坑 / 刷墙类贪心
易错点
- 不要枚举区间。 最大到 ,模拟每一天的填充会超时。
- 可能为 0。如果第一块就是 ,,答案从 开始累加,不影响正确性。
- 答案最大为 ,在
int范围内(约 ),无需long long。
