最新华为OD机试真题-K小姐的画图机器(100分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> K小姐的画图机器(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

☕️ K小姐的画图机器

问题描述

K小姐有一台特殊的画图机器，该机器初始时画笔位于坐标原点 。机器启动后，画笔会先沿着 轴正方向移动，直到到达给定的终点坐标 。在移动过程中，可以通过一些指令控制画笔在 轴方向上的偏移，同时画笔也会留下它移动的轨迹。

每条指令包含两个整数 和 ，表示当画笔横坐标到达 时，画笔在 轴方向上偏移 个单位距离（正数表示正向偏移，负数表示负向偏移）。

现给定横坐标终点值 以及若干条画笔偏移指令，请你计算画笔最终绘制的图形和横坐标轴及竖直线 围成的区域面积。

输入格式

第一行包含两个整数 和 ，分别表示指令的条数和画笔运行的横坐标终点值。

接下来 行，每行两个整数 和 ，表示一条画笔偏移指令。保证 严格递增，且不会出现相同的 。

输出格式

输出一个整数，表示画笔绘制的图形和横坐标轴及竖直线 围成的区域面积。

样例输入

4 10
1 1
2 1
3 1 
4 -2

样例输出

12

样例输入

2 4
0 1
2 -2

样例输出

4

数据范围

题解

本题的关键是计算画笔经过的每个横坐标区间与 轴围成的面积，然后将所有区间的面积累加起来即可得到最终答案。

具体做法如下：

1. 用变量 和 分别记录上一个指令的横坐标和截止到上一个指令时的 坐标。初始时 ，。

2. 遍历每一条指令 ：

   • 当前指令的横坐标为 ，上一条指令的横坐标为 ，则画笔在区间 上移动，且这个区间内 坐标始终为 。因此该区间与 轴围成的面积为 ，将其累加到答案中。
   • 然后用 加上 ，即可得到截止到当前指令时的 坐标。
   • 再将 更新为 。

3. 遍历完所有指令后，若 ，说明还有一段区间 未被计算，需要将这段区间的面积 累加到答案中。

4. 最终输出答案即可。

算法的时间复杂度为 ，空间复杂度为 。

参考代码

• Python

N, E = map(int, input().split())

ans = 0
last_x, last_y = 0, 0

for _ in range(N):
    X, offset_y = map(int, input().split())
    ans += (X - last_x) * abs(last_y)
    last_x, last_y = X, last_y + offset_y

if E > last_x:
    ans += (E - last_x) * abs(last_y)

print(ans)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int E = sc.nextInt();
        
        long ans = 0;
        long lastX = 0, lastY = 0;
        
        for (int i = 0; i < N; i++) {
            int X = sc.nextInt();
            int offsetY = sc.nextInt();
            ans += (X - lastX) * Math.abs(lastY);
            lastX = X;
            lastY += offsetY;
        }
        
        if (E > lastX) {
            ans += (E - lastX) * Math.abs(lastY);
        }
        
        System.out.println(ans);
    }
}

• Cpp

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int N, E;
    cin >> N >> E;
    
    long long ans = 0;
    int lastX = 0, lastY = 0;
    
    while (N--) {
        int X, offsetY;
        cin >> X >> offsetY;
        ans += (X - lastX) * abs(lastY);
        lastX = X;
        lastY += offsetY;
    }
    
    if (E > lastX) {
        ans += (E - lastX) * abs(lastY);
    }
    
    cout << ans << endl;
    
    return 0;
}