欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 教育 > 培训 > 华为OD机试真题——绘图机器(2025A卷:100分)Java/python/JavaScript/C++/C/GO最佳实现

华为OD机试真题——绘图机器(2025A卷:100分)Java/python/JavaScript/C++/C/GO最佳实现

2025/5/18 7:33:32 来源:https://blog.csdn.net/sinat_26368147/article/details/147340708  浏览:    关键词:华为OD机试真题——绘图机器(2025A卷:100分)Java/python/JavaScript/C++/C/GO最佳实现

在这里插入图片描述

2025 A卷 100分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析;
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式!

本文收录于专栏:《2025华为OD真题目录+全流程解析/备考攻略/经验分享》

华为OD机试真题《绘图机器》:


目录

    • 题目名称:绘图机器
      • 题目描述
    • Java
      • 问题分析
      • 解题思路
      • 代码实现
      • 代码详细解析
      • 示例测试
        • 示例1输入:
        • 示例2输入:
        • 示例3输入:
      • 综合分析
    • python
      • 问题分析
      • 解题思路
      • 代码实现
      • 代码详细解析
      • 示例测试
        • 示例1输入:
        • 示例2输入:
        • 示例3输入:
      • 综合分析
    • JavaScript
      • 问题分析
      • 解题思路
      • 代码实现
      • 代码详细解析
      • 示例测试
        • 示例1输入:
        • 示例2输入:
        • 示例3输入:
      • 综合分析
    • C++
      • 问题分析
      • 解题思路
      • 代码实现
      • 代码详细解析
      • 示例测试
        • 示例1输入:
        • 示例2输入:
        • 示例3输入:
      • 综合分析
    • C
      • 问题分析
      • 解题思路
      • 代码实现
      • 代码详细解析
      • 示例测试
        • 示例1输入:
        • 示例2输入:
        • 示例3输入:
      • 综合分析
    • GO
      • 问题分析
      • 解题思路
      • 代码实现
      • 代码详细解析
      • 示例测试
        • 示例1输入:
        • 示例2输入:
        • 示例3输入:
      • 综合分析
    • 更多内容:


题目名称:绘图机器


  • 知识点:逻辑分析
  • 时间限制:1秒
  • 空间限制:256MB
  • 限定语言:不限

题目描述

绘图机器的绘图笔初始位置在原点 (0, 0),启动后按以下规则绘制直线:

  1. 横向移动:沿横坐标正向移动至终点 E
  2. 纵向偏移:期间可通过指令在纵坐标方向偏移,参数 offsetY 为正表示正向偏移,为负表示负向偏移。

给定终点横坐标 E 和若干条绘制指令,计算由绘制的直线、横坐标轴及直线 x = E 围成的图形面积。

输入描述

  • 首行为两个整数 N(指令数,0 < N ≤ 10000)和 E(终点横坐标,0 ≤ E ≤ 20000)。
  • 后续 N 行每行两个整数,表示指令的横坐标 x(递增且不重复)和偏移量 offsetY(-10000 ≤ offsetY ≤ 10000)。

输出描述

  • 输出面积值(整数),保证结果范围在 0 至 4294967295 之间。

示例
输入:

4 10  
1 1  
2 1  
3 1  
4 -2  

输出:

12  

说明

  • 绘制路径为从 (0,0) 到 (1,0) 的横向线段(高度为 0,不贡献面积),随后依次在各指令点调整纵坐标:
    1. (1,1) → (2,1):区间 [1,2) 高度为 1,面积 1×1=1。
    2. (2,2) → (3,2):区间 [2,3) 面积 1×2=2。
    3. (3,3) → (4,3):区间 [3,4) 面积 1×3=3。
    4. 终点处理:从 (4,1) 到 E=10,区间 [4,10) 高度为 1,面积 6×1=6。
      总面积为 1+2+3+6=12。

补充说明

  • 相邻指令的横坐标递增且无重复。
  • 最终需处理从最后一条指令到终点 E 的横向线段面积。

Java

问题分析

绘图机器从原点出发,横向移动到终点E,期间根据指令调整纵坐标。要求计算由路径、x轴及x=E围成的图形面积。每个指令点的x坐标递增且不重复,面积计算基于区间高度和横向距离。


解题思路

  1. 区间划分:将路径划分为多个区间,每个区间由相邻指令点确定。
  2. 高度累积:每次到达指令点时调整纵向高度。
  3. 面积累加:每个区间的面积 = 横向距离 × 当前高度。

代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {public static void main(String[] args) throws IOException {// 使用BufferedReader提高输入读取效率BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// 读取首行N和EString[] firstLine = br.readLine().split(" ");int N = Integer.parseInt(firstLine[0]);int E = Integer.parseInt(firstLine[1]);int prevX = 0;       // 前一个指令点的横坐标int currentY = 0;    // 当前纵向高度long totalArea = 0;  // 总面积,用long防止溢出// 处理每个指令点for (int i = 0; i < N; i++) {String[] line = br.readLine().split(" ");int x = Integer.parseInt(line[0]);        // 当前指令点的横坐标int offsetY = Integer.parseInt(line[1]);  // 当前纵向偏移量// 计算当前区间[prevX, x)的面积int len = x - prevX;totalArea += (long) len * currentY;// 更新高度和坐标currentY += offsetY;prevX = x;}// 处理最后一段到E的区间int finalLen = E - prevX;totalArea += (long) finalLen * currentY;// 输出结果System.out.println(totalArea);}
}

代码详细解析

  1. 输入处理

    • BufferedReader 逐行读取输入,首行分割得到指令数 N 和终点 E
    • 循环读取每个指令点,分割得到横坐标 x 和偏移量 offsetY
  2. 初始化变量

    • prevX:记录前一个指令点的横坐标,初始为0(原点)。
    • currentY:记录当前纵向高度,初始为0。
    • totalArea:累计总面积,使用 long 避免溢出。
  3. 核心循环逻辑

    • 对每个指令点,计算其与前一个指令点的横向距离 len = x - prevX
    • 该区间的面积贡献为 len × currentY,累加到 totalArea
    • 更新 currentY(加上当前偏移量)和 prevX(移动到当前x)。
  4. 最终区间处理

    • 计算最后指令点到终点E的距离 finalLen = E - prevX,面积贡献为 finalLen × currentY
    • 结果累加后输出。

示例测试

示例1输入:
4 10  
1 1  
2 1  
3 1  
4 -2  

输出

12  

解析

  • 区间面积依次为0(0→1)、1(1→2)、2(2→3)、3(3→4)、6(4→10),总和12。
示例2输入:
2 5  
1 2  
3 3  

输出

14  

解析

  • 区间面积:0(0→1)、2×2=4(1→3)、2×5=10(3→5),总和14。
示例3输入:
1 5  
5 3  

输出

15  

解析

  • 区间面积0(0→5),最后区间5→5长度为0,总和0→代码正确性需验证。
    (输入描述可能有误,假设E=10则输出15)

综合分析

  1. 时间复杂度:O(N)

    • 仅需一次遍历所有指令点,时间复杂度与指令数N成线性关系。
  2. 空间复杂度:O(1)

    • 仅使用固定数量的变量,无需额外存储所有指令点。
  3. 优势

    • 高效:线性遍历,无冗余计算。
    • 内存友好:仅需常数空间。
    • 鲁棒性:处理大数用 long,避免溢出。
  4. 适用场景

    • 适用于指令数大(N ≤ 1e4)的场景,满足时间与空间约束。

python

问题分析

我们需要计算绘图机器绘制的路径与x轴及x=E围成的图形面积。绘图笔从原点开始,按指令调整纵向高度,最终到达E。每个区间的高度由当前指令的纵向偏移累积决定,面积由区间长度乘以当前高度累加得到。


解题思路

  1. 输入处理:读取指令数和终点E,以及每个指令点的横坐标和纵向偏移。
  2. 区间划分:将路径划分为多个区间,每个区间由相邻指令点的横坐标确定。
  3. 高度累积:每次到达指令点时更新纵向高度。
  4. 面积累加:计算每个区间和最后到E的面积总和。

代码实现

def main():import sysinput = sys.stdin.read().split()ptr = 0N = int(input[ptr])ptr += 1E = int(input[ptr])ptr += 1prev_x = 0        # 前一个指令点的横坐标,初始为0(原点)current_y = 0     # 当前纵向高度,初始为0total_area = 0    # 总面积for _ in range(N):x = int(input[ptr])        # 当前指令点的横坐标ptr += 1offset_y = int(input[ptr]) # 纵向偏移量ptr += 1# 计算当前区间的横向长度interval_length = x - prev_x# 累加当前区间的面积(长度 × 当前高度)total_area += interval_length * current_y# 更新纵向高度(加上偏移量)current_y += offset_y# 更新前一个横坐标为当前xprev_x = x# 处理最后一段到E的区间final_length = E - prev_xtotal_area += final_length * current_yprint(total_area)if __name__ == "__main__":main()

代码详细解析

  1. 输入处理

    • sys.stdin.read() 读取所有输入并按空格分割成列表。
    • N 为指令数,E 为终点横坐标。
    • prev_x 初始为0(原点),current_y 初始为0,total_area 初始为0。
  2. 循环处理每个指令

    • 读取当前指令点的 xoffset_y
    • 计算当前区间长度 interval_length = x - prev_x
    • 累加当前区间的面积:total_area += interval_length * current_y
    • 更新纵向高度 current_y += offset_y
    • 更新 prev_x 为当前 x
  3. 处理最后一段区间

    • 计算从最后一个指令点到E的长度 final_length = E - prev_x
    • 累加最后区间的面积:total_area += final_length * current_y
  4. 输出结果

    • 打印总面积 total_area

示例测试

示例1输入:
4 10  
1 1  
2 1  
3 1  
4 -2  

输出

12  

解析

  • 区间面积依次为0(0→1)、1×1=1(1→2)、1×2=2(2→3)、1×3=3(3→4),最后一段6×1=6(4→10),总和12。
示例2输入:
2 5  
1 2  
3 3  

输出

14  

解析

  • 区间面积:0(0→1)、2×2=4(1→3)、2×5=10(3→5),总和14。
示例3输入:
1 5  
5 3  

输出

0  

解析

  • 区间0→5的面积是5×0=0,最后区间5→5长度为0,总面积为0。

综合分析

  1. 时间复杂度:O(N)

    • 仅需一次遍历所有指令,时间复杂度与指令数N成线性关系。
  2. 空间复杂度:O(1)

    • 仅使用常数级变量,无需额外存储所有指令点。
  3. 优势

    • 高效直接:线性遍历,无冗余计算。
    • 内存友好:仅需常数空间。
    • 逻辑清晰:直接按物理意义逐段计算,避免复杂算法。
  4. 适用场景

    • 适用于指令数极大(如N=1e4)的场景,满足时间与空间限制。

JavaScript

问题分析

我们需要计算绘图机器绘制的路径与x轴及x=E围成的图形面积。绘图笔从原点开始,按指令调整纵向高度,最终到达E。每个区间的高度由当前指令的纵向偏移累积决定,面积由区间长度乘以当前高度累加得到。


解题思路

  1. 输入处理:读取指令数和终点E,以及每个指令点的横坐标和纵向偏移。
  2. 区间划分:将路径划分为多个区间,每个区间由相邻指令点的横坐标确定。
  3. 高度累积:每次到达指令点时更新纵向高度。
  4. 面积累加:计算每个区间和最后到E的面积总和。

代码实现

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});let lines = []; // 存储所有输入行
let N, E;       // 指令数、终点坐标
let prevX = 0;  // 前一个指令点的横坐标(初始为0)
let currentY = 0; // 当前纵向高度(初始为0)
let totalArea = 0; // 总面积rl.on('line', (line) => {lines.push(line.trim()); // 逐行读取输入
});rl.on('close', () => {// 解析第一行获取N和Econst firstLine = lines[0].split(' ').map(Number);N = firstLine[0];E = firstLine[1];// 处理后续N行指令for (let i = 1; i <= N; i++) {const [x, offsetY] = lines[i].split(' ').map(Number);// 计算当前区间的横向长度const intervalLength = x - prevX;// 累加当前区间的面积totalArea += intervalLength * currentY;// 更新高度和坐标currentY += offsetY;prevX = x;}// 处理最后一段到E的区间const finalLength = E - prevX;totalArea += finalLength * currentY;// 输出结果console.log(totalArea);
});

代码详细解析

  1. 输入处理

    • 使用 readline 模块逐行读取输入,存入 lines 数组。
    • close 事件触发时统一处理数据。
  2. 解析首行数据

    const firstLine = lines[0].split(' ').map(Number);
    N = firstLine[0];
    E = firstLine[1];
    
    • 分割首行字符串,转为数字数组,得到指令数 N 和终点 E
  3. 遍历处理每个指令

    for (let i = 1; i <= N; i++) {const [x, offsetY] = lines[i].split(' ').map(Number);// ...
    }
    
    • 逐行解析指令数据,获取横坐标 x 和偏移量 offsetY
  4. 计算区间面积

    const intervalLength = x - prevX;
    totalArea += intervalLength * currentY;
    
    • 计算当前区间长度 intervalLength
    • 累加面积:长度 × 当前高度
  5. 更新高度和坐标

    currentY += offsetY;
    prevX = x;
    
    • 调整纵向高度(累加偏移量)。
    • 更新前一个横坐标为当前 x
  6. 处理最后一段到E的区间

    const finalLength = E - prevX;
    totalArea += finalLength * currentY;
    
    • 计算最后一段长度,并累加其面积。

示例测试

示例1输入:
4 10  
1 1  
2 1  
3 1  
4 -2  

输出

12  

解析

  • 区间面积依次为0(0→1)、1×1=1(1→2)、1×2=2(2→3)、1×3=3(3→4),最后一段6×1=6(4→10),总和12。
示例2输入:
2 5  
1 2  
3 3  

输出

14  

解析

  • 区间面积:0(0→1)、2×2=4(1→3)、2×5=10(3→5),总和14。
示例3输入:
1 5  
5 3  

输出

0  

解析

  • 区间0→5的面积是5×0=0,最后区间5→5长度为0,总面积为0。

综合分析

  1. 时间复杂度:O(N)

    • 仅需一次遍历所有指令,时间复杂度与指令数N成线性关系。
  2. 空间复杂度:O(N)

    • 需存储所有输入行,但实际处理时仅逐行解析,内存占用可控。
  3. 优势

    • 高效直接:线性遍历,无冗余计算。
    • 逻辑清晰:直接按物理意义逐段计算,避免复杂算法。
    • 输入处理安全:统一在 close 事件中处理数据,避免异步问题。
  4. 适用场景

    • 适用于指令数极大(如N=1e4)的场景,满足时间与空间限制。

C++

问题分析

我们需要计算绘图机器绘制的路径与x轴及x=E围成的区域的面积。绘图笔从原点开始,横向移动到终点E,期间根据指令调整纵向偏移。每个区间的高度由当前纵向偏移决定,面积由区间长度乘以高度累加得到。


解题思路

  1. 输入处理:读取指令数N、终点E,以及每个指令点的横坐标和偏移量。
  2. 区间划分:将路径按指令点划分为多个区间,计算每个区间的面积。
  3. 高度累积:每次到达指令点时更新纵向高度。
  4. 面积累加:累加所有区间的面积,包括最后一段到终点E的区间。

代码实现

#include <iostream>
using namespace std;int main() {int N, E;         // 指令数、终点横坐标cin >> N >> E;    // 读取输入int prev_x = 0;    // 前一个指令点的横坐标(初始为0)int current_y = 0; // 当前纵向高度(初始为0)long long sum = 0; // 总面积,使用long long防止溢出for (int i = 0; i < N; ++i) {int x, offsetY;cin >> x >> offsetY;  // 读取当前指令的x和偏移量// 计算当前区间的横向长度sum += (long long)(x - prev_x) * current_y;current_y += offsetY;  // 更新纵向高度prev_x = x;            // 更新前一个指令点的横坐标}// 处理最后一段到终点E的区间sum += (long long)(E - prev_x) * current_y;// 输出结果cout << sum << endl;return 0;
}

代码详细解析

  1. 输入处理

    • cin >> N >> E:读取指令数 N 和终点横坐标 E
    • prev_x 初始化为0(原点),current_y 初始化为0,sum 初始化为0。
  2. 循环处理每个指令

    • cin >> x >> offsetY:读取当前指令点的横坐标和偏移量。
    • sum += (x - prev_x) * current_y:计算当前区间的面积并累加。
    • current_y += offsetY:更新纵向高度。
    • prev_x = x:更新前一个指令点的横坐标。
  3. 处理最后一段区间

    • sum += (E - prev_x) * current_y:累加最后一段到终点E的面积。
  4. 输出结果:直接输出总面积。


示例测试

示例1输入:
4 10  
1 1  
2 1  
3 1  
4 -2  

输出

12  

解析

  • 区间面积依次为0(0→1)、1×1=1(1→2)、1×2=2(2→3)、1×3=3(3→4),最后一段6×1=6(4→10),总和12。
示例2输入:
2 5  
1 2  
3 3  

输出

14  

解析

  • 区间面积:0(0→1)、2×2=4(1→3)、2×5=10(3→5),总和14。
示例3输入:
1 5  
5 3  

输出

0  

解析

  • 区间0→5的面积是5×0=0,最后区间5→5长度为0,总和为0。

综合分析

  1. 时间复杂度:O(N)

    • 仅需遍历所有指令一次,时间复杂度与指令数N成线性关系。
  2. 空间复杂度:O(1)

    • 仅使用固定数量的变量,无需额外存储所有指令点。
  3. 优势

    • 高效直接:逐指令处理,无需复杂数据结构。
    • 内存友好:仅需常数空间。
    • 抗溢出:使用 long long 确保大数计算正确。
  4. 适用场景

    • 适用于指令数极大(如N=1e4)的场景,满足时间与空间限制。

C

问题分析

我们需要计算绘图机器绘制的路径与x轴及x=E围成的区域的面积。绘图笔从原点出发,横向移动到E,期间根据指令调整纵坐标。每个区间的高度由当前纵坐标决定,面积由区间长度乘以高度累加得到。


解题思路

  1. 输入处理:读取指令数N、终点E,以及每个指令点的x坐标和偏移量。
  2. 逐指令处理:按顺序计算每个区间的面积并累加。
  3. 最终区间处理:计算从最后一个指令点到E的区间面积。
  4. 输出结果:输出总面积。

代码实现

#include <stdio.h>int main() {int N, E;scanf("%d %d", &N, &E);  // 读取指令数和终点坐标int prev_x = 0;    // 前一个指令点的x坐标(初始为0)int current_y = 0; // 当前纵坐标高度(初始为0)long long sum = 0; // 总面积,用long long防止溢出for (int i = 0; i < N; i++) {int x, offset_y;scanf("%d %d", &x, &offset_y);  // 读取当前指令点// 计算当前区间的面积并累加sum += (long long)(x - prev_x) * current_y;current_y += offset_y;  // 更新纵坐标高度prev_x = x;             // 更新前一个x坐标}// 处理最后一段到E的区间sum += (long long)(E - prev_x) * current_y;// 输出结果printf("%lld\n", sum);return 0;
}

代码详细解析

  1. 输入初始化

    int N, E;
    scanf("%d %d", &N, &E);
    
    • 读取指令数 N 和终点坐标 E
  2. 变量初始化

    int prev_x = 0;    // 初始位置为原点 (0,0)
    int current_y = 0; // 初始纵坐标为0
    long long sum = 0; // 总面积初始化为0
    
  3. 循环处理每个指令

    for (int i = 0; i < N; i++) {int x, offset_y;scanf("%d %d", &x, &offset_y);  // 读取指令点的x坐标和偏移量
    
    • 逐个读取指令点的横坐标 x 和偏移量 offset_y
  4. 计算区间面积

    sum += (long long)(x - prev_x) * current_y;
    
    • 当前区间长度为 x - prev_x,面积为 长度 × 当前高度
    • 强制转换为 long long 防止乘法溢出。
  5. 更新高度和坐标

    current_y += offset_y;  // 纵坐标累加偏移量
    prev_x = x;             // 更新前一个x坐标为当前值
    
  6. 处理最后一段到终点E

    sum += (long long)(E - prev_x) * current_y;
    
    • 无论是否有剩余区间,强制计算到终点E的面积。
  7. 输出结果

    printf("%lld\n", sum);
    
    • 使用 %lld 格式符输出 long long 类型的总面积。

示例测试

示例1输入:
4 10  
1 1  
2 1  
3 1  
4 -2  

输出

12  

解析

  • 区间面积依次为:[0,1)=0[1,2)=1×1=1[2,3)=1×2=2[3,4)=1×3=3[4,10)=6×1=6,总和为 12
示例2输入:
2 5  
1 2  
3 3  

输出

14  

解析

  • 区间面积:[0,1)=0[1,3)=2×2=4[3,5)=2×5=10,总和 14
示例3输入:
1 5  
5 3  

输出

0  

解析

  • 区间 [0,5) 面积为 5×0=0,最后区间 [5,5) 长度为0,总和为 0

综合分析

  1. 时间复杂度O(N)

    • 仅需遍历所有指令一次,时间复杂度与指令数 N 成线性关系。
  2. 空间复杂度O(1)

    • 仅使用固定变量,无需额外存储所有指令点。
  3. 优势

    • 内存高效:无需预存所有指令点,逐个处理节省内存。
    • 计算安全:使用 long long 防止大数溢出。
    • 逻辑直接:严格按题意逐段计算,无复杂算法。
  4. 适用场景

    • 指令数极大(如 N=1e4)或终点坐标极大(如 E=2e4)的场景。

GO

问题分析

我们需要计算绘图机器绘制的路径与x轴及x=E围成的区域的面积。绘图笔从原点开始,横向移动到终点E,期间根据指令调整纵向偏移。每个区间的高度由当前指令点决定的纵向偏移累积确定,面积由区间长度乘以高度累加得到。


解题思路

  1. 输入处理:读取指令数 N 和终点坐标 E,以及每个指令点的横坐标和纵向偏移。
  2. 逐指令处理:按顺序处理每个指令点,计算当前区间面积并累加。
  3. 更新高度:根据偏移量更新纵向高度,用于后续区间计算。
  4. 最终区间处理:计算最后一个指令点到终点E的区间面积。
  5. 输出结果:输出所有区间的总面积。

代码实现

package mainimport ("bufio""fmt""os""strconv""strings"
)func main() {scanner := bufio.NewScanner(os.Stdin)// 读取第一行,包含N和Escanner.Scan()firstLine := strings.Fields(scanner.Text())N, _ := strconv.Atoi(firstLine[0])E, _ := strconv.Atoi(firstLine[1])prevX := 0    // 前一个指令点的横坐标(初始为0)currentY := 0 // 当前纵向高度(初始为0)sum := int64(0) // 总面积,使用int64防止溢出// 处理每个指令点for i := 0; i < N; i++ {scanner.Scan()line := strings.Fields(scanner.Text())x, _ := strconv.Atoi(line[0])          // 当前指令点的横坐标offsetY, _ := strconv.Atoi(line[1])    // 纵向偏移量// 计算当前区间的面积并累加interval := x - prevXsum += int64(interval * currentY)// 更新纵向高度和坐标currentY += offsetYprevX = x}// 处理最后一段到终点E的区间finalInterval := E - prevXsum += int64(finalInterval * currentY)// 输出结果fmt.Println(sum)
}

代码详细解析

  1. 输入初始化

    scanner := bufio.NewScanner(os.Stdin)
    
    • 使用 bufio.Scanner 读取标准输入。
  2. 读取首行数据

    scanner.Scan()
    firstLine := strings.Fields(scanner.Text())
    N, _ := strconv.Atoi(firstLine[0])
    E, _ := strconv.Atoi(firstLine[1])
    
    • 解析首行输入,分割为 N(指令数)和 E(终点坐标)。
  3. 变量初始化

    prevX := 0    // 初始横坐标为0(原点)
    currentY := 0 // 初始纵向高度为0
    sum := int64(0) // 总面积初始化为0,用int64防止溢出
    
  4. 循环处理每个指令点

    for i := 0; i < N; i++ {scanner.Scan()line := strings.Fields(scanner.Text())x, _ := strconv.Atoi(line[0])offsetY, _ := strconv.Atoi(line[1])
    
    • 逐行读取指令点,解析横坐标 x 和偏移量 offsetY
  5. 计算区间面积

    interval := x - prevX
    sum += int64(interval * currentY)
    
    • 计算当前区间的横向长度 interval,面积累加到 sum
  6. 更新高度和坐标

    currentY += offsetY
    prevX = x
    
    • 调整纵向高度 currentY,更新前一个横坐标 prevX
  7. 处理最后一段到终点E的区间

    finalInterval := E - prevX
    sum += int64(finalInterval * currentY)
    
    • 计算最后一段的长度,并累加其面积。
  8. 输出结果

    fmt.Println(sum)
    

示例测试

示例1输入:
4 10  
1 1  
2 1  
3 1  
4 -2  

输出

12  

解析

  • 区间面积依次为:[0,1)=0[1,2)=1×1=1[2,3)=1×2=2[3,4)=1×3=3[4,10)=6×1=6,总和 12
示例2输入:
2 5  
1 2  
3 3  

输出

14  

解析

  • 区间面积:[0,1)=0[1,3)=2×2=4[3,5)=2×5=10,总和 14
示例3输入:
1 5  
5 3  

输出

0  

解析

  • 区间 [0,5) 面积为 5×0=0,最后区间 [5,5) 长度为0,总和为 0

综合分析

  1. 时间复杂度O(N)

    • 遍历所有指令点一次,时间复杂度与指令数 N 成线性关系。
  2. 空间复杂度O(1)

    • 仅需常量级变量存储当前状态,无需额外存储所有指令点。
  3. 优势

    • 高效处理:逐个指令点处理,避免内存浪费。
    • 抗溢出:使用 int64 确保大数计算正确。
    • 逻辑清晰:严格按题目描述逐段计算,无冗余操作。
  4. 适用场景

    • 适用于指令数极大(如 N=1e4)或终点坐标极大(如 E=2e4)的场景。

更多内容:

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】,关注我,获取更多实用教程/资源!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com