最新华为OD机试真题-K小姐的画图机器(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
☕️ K小姐的画图机器
问题描述
K小姐有一台特殊的画图机器,该机器初始时画笔位于坐标原点 。机器启动后,画笔会先沿着 轴正方向移动,直到到达给定的终点坐标 。在移动过程中,可以通过一些指令控制画笔在 轴方向上的偏移,同时画笔也会留下它移动的轨迹。
每条指令包含两个整数 和 ,表示当画笔横坐标到达 时,画笔在 轴方向上偏移 个单位距离(正数表示正向偏移,负数表示负向偏移)。
现给定横坐标终点值 以及若干条画笔偏移指令,请你计算画笔最终绘制的图形和横坐标轴及竖直线 围成的区域面积。
输入格式
第一行包含两个整数 和 ,分别表示指令的条数和画笔运行的横坐标终点值。
接下来 行,每行两个整数 和 ,表示一条画笔偏移指令。保证 严格递增,且不会出现相同的 。
输出格式
输出一个整数,表示画笔绘制的图形和横坐标轴及竖直线 围成的区域面积。
样例输入
4 10
1 1
2 1
3 1
4 -2
样例输出
12
样例输入
2 4
0 1
2 -2
样例输出
4
数据范围
题解
本题的关键是计算画笔经过的每个横坐标区间与 轴围成的面积,然后将所有区间的面积累加起来即可得到最终答案。
具体做法如下:
-
用变量 和 分别记录上一个指令的横坐标和截止到上一个指令时的 坐标。初始时 ,。
-
遍历每一条指令 :
- 当前指令的横坐标为 ,上一条指令的横坐标为 ,则画笔在区间 上移动,且这个区间内 坐标始终为 。因此该区间与 轴围成的面积为 ,将其累加到答案中。
- 然后用 加上 ,即可得到截止到当前指令时的 坐标。
- 再将 更新为 。
-
遍历完所有指令后,若 ,说明还有一段区间 未被计算,需要将这段区间的面积 累加到答案中。
-
最终输出答案即可。
算法的时间复杂度为 ,空间复杂度为 。
参考代码
- Python
N, E = map(int, input().split())
ans = 0
last_x, last_y = 0, 0
for _ in range
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测