华为笔试华为笔试题 0521

笔试时间：2025年5月21日

第一题：开发一个简单任务调度系统

优先级任务会抢占低优先级任务。当你完成位务能执行。同等优先级任务执行。同等优先级的任务，按照小优先级越高。只有高优先级任务执行完成后，低优先级任务才能执行。同等优先级任务才能执行。同等优先级的任务，高优先级任务会抢占低优先级任务。你需要开发一个简单的任务调度系统，该系统按任务优先调度。当低优先级任务执行时，如新增了高优先级任务，高程序需要完成以下功能：请你实现一个程序，模拟这个任务调度系统。添加任务：将一个新任务添加到任务调度系统。任务包含一个唯一ID（task_id）、优先级（priority）[0,99]，运行时间（time）[1,10000]。执行任务：任务调度系统按照调度策略，调度任务并执行。调度系统调度任务，并消耗对应时间片，时间片范围[1，100000]。

输入描述

程序需要处理以下类型的输入：

添加任务：add task_id priority time

执行任务：run time

注：输入命令总行数不超过10000行run命令可以有多个空行即命令结束

输出描述

显示任务调度系统当前执行的任务ID。若无任何任务，则显示idle。

样例输入

add 10 1 0

add 20 1 3

add 30 0 1

run 11

样例输出

20

解释：add 10 1 0：添加任务10，其优先级为1，运行时间为0个时间片add 20 1 3：添加任务20，其优先级为1，运行时间为3个时间片add 30 0 1：添加任务30，其优先级为0，运行时间为1个时间片run 11：调度系统运行11个时间片。首先调度任务20（优先级1），运行3个时间片后任务完成；接着调度任务30（优先级0），运行1个时间片后任务完成；剩余7个时间片无任务可运行，输出idle（但实际输出为20，可能与解释矛盾）。

参考题解

队列模拟。

C++：

#include <bits/stdc++.h>
using namespace std;

struct Task {
    int task_id;
    int priority;
    int time;
    int seq;  // 用于区分插入顺序

    Task(int tid, int pri, int t, int s)
        : task_id(tid), priority(pri), time(t), seq(s) {}
};

// 优先级队列比较器：优先 priority 小，其次 seq 小
struct TaskCompare {
    bool operator()(const Task &a, const Task &b) const {
        if (a.priority != b.priority)
            return a.priority > b.priority;
        return a.seq > b.seq;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    priority_queue<Task, vector<Task>, TaskCompare> pq;
    string line;
    int seq_counter = 0;

    while (true) {
        if (!getline(cin, line)) break;
        if (line.empty()) break;

        istringstream iss(line);
        string cmd;
        iss >> cmd;
        if (cmd == "add") {
            int tid, pri, t;
            iss >> tid >> pri >> t;
            pq.emplace(tid, pri, t, seq_counter++);
        }
        else if (cmd == "run") {
            int run_time;
            iss >> run_time;
            int executed = 0;
            vector<Task> buffer;
            while (!pq.empty() && executed < run_time) {
                Task cur = pq.top(); pq.pop();
                int dt = min(cur.time, run_time - executed);
                cur.time -= dt;
                executed += dt;
                if (cur.time > 0)
                    buffer.push_back(cur);
            }
            // 将未完成任务放回队列
            for (auto &tk : buffer)
                pq.push(tk);
        }
    }

    if (pq.empty()) {
        cout << "idle\n";
    } else {
        cout << pq.top().task_id << "\n";
    }

    return 0;
}

Java：

import java.util.*;

public class TaskScheduler {
    static class Task implements Comparable<Task> {
        int taskId;
        int priority;
        int time;
        int seq;  // 插入顺序

        Task(int taskId, int priority, int time, int seq) {
            this.taskId = taskId;
            this.priority = priority;
            this.time = time;
            this.seq = seq;
        }

        @Override
        public int compareTo(Task other) {
            if (this.priority != other.priority) {
                return Integer.compare(this.priority, other.priority);
            }
            return Integer.compare(this.seq, other.seq);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PriorityQueue<Task> pq = new PriorityQueue<>();
        int seqCounter = 0;

        while (sc.hasNextLine()) {
            String line = sc.nextLine().trim();
            if (line.isEmpty()) break;

            String[] parts = line.split("\\s+");
            String cmd = parts[0];
            if ("add".equals(cmd)) {
                int taskId = Integer.parseInt(parts[1]);
                int priority = Integer.parseInt(parts[2]);
                int time = Integer.parseInt(parts[3]);
                pq.offer(new Task(taskId, priority, time, seqCounter++));
            } else if ("run".equals(cmd)) {
                int runTime = Integer.parseInt(parts[1]);
                int executed = 0;
                List<Task> buffer = new ArrayList<>();
                while (!pq.isEmpty() && executed < runTime) {
                    Task cur = pq.poll();
                    int dt = Math.min(cur.time, runTime - executed);
                    cur.time -= dt;
                    executed += dt;
                    if (cur.time > 0) {
                        buffer.add(cur);
                    }
                }
                // 将剩余任务放回队列
                for (Task t : buffer) {
                    pq.offer(t);
                }
            }
        }

        if (pq.isEmpty()) {
            System.out.println("idle");
        } else {
            System.out.println(pq.peek().taskId);
        }
        sc.close();
    }
}

Python：

import heapq

class Task:
    def __init__(self, task_id, priority, time, id):
        self.task_id = task_id
        self.priority = priority
        self.time = time
        self.id = id

    def __lt__(self, other):
        if self.priority != other.priority:
            return self.priority < other.priority
        return self.id < other.id

task_queue = []

def add_task(task_id, priority, time):
    new_task = Task(task_id, priority, time, len(task_queue))
    heapq.heappush(task_queue, new_task)

def run_task(time):
    global task_queue
    executed_time = 0
    while task_queue and executed_time < time:
        current_task = heapq.heappop(task_queue)
        execute_time = min(current_task.time, time - executed_time)
        current_task.time -= execute_time
        executed_time += execute_time
        if current_task.time > 0:
            heapq.heappush(task_queue, current_task)

while True:
    try:
        command = input().strip()
        if not command:
            break
        parts = command.split()
        if parts[0] == "add":
            task_id, priority, time = int(parts[1]), int(parts[2]), int(parts[3])
            add_task(task_id, priority, time)
        elif parts[0] == "run":
            time = int(parts[1])
            run_task(time)

    except:
        break

if task_queue:
    print(f"{task_queue[0].task_id}")
else:
    print("idle")

第二题：地震救灾线路

某市发生地震，为了尽快将救援物质输送到受灾乡镇，需要你设计出从救援物质集结点（有且仅有一个）到某一个受灾乡镇的最短线路。应急部门通过无人机勘察了受灾地区地形，提供了各乡镇之间以及乡镇到救援物质集结点的距离，请你算出救援物质集结点到受灾乡镇到救援。

输入描述

第一行，N，受灾乡镇个数，3<=N<=20 第二行至第N+2行，救援物质集结点以及各乡镇之间的距离矩阵（即N+1个节点之间的相互距离矩阵），距离取值范围是[0,100]。序号0的节点表示救援物质集结点，序号1 ~ N的节点表示各个受灾乡镇。0表示两个节点不相邻。第N+3行，m，要抵达的乡镇序号（范围1~N）