最新华为OD机试真题-任务积分优化问题(100分)

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

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

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 任务积分优化问题(100分) <=

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

🍓OJ题目截图

🌲 任务积分优化问题

问题描述

K小姐在一家公司负责完成一系列任务，每个任务都有一个最晚完成时间和相应的积分奖励。现在，K小姐想知道在有限的时间内，她最多能获得多少积分。

输入格式

第一行包含一个整数 ，表示任务的数量。

第二行包含一个整数 ，表示可用于处理任务的时间。

接下来 行，每行两个整数 和 ，分别代表任务的最晚处理时间和任务的积分值。

输出格式

输出一个整数，表示在限定的时间内能获得的最大积分。

样例输入

4
3
1 2
1 3
1 4
1 5

样例输出

5

数据范围

题解

本题是一个经典的贪心选择问题，目标是在有限的时间内完成尽可能多的积分。由于每个任务都需要一个单位时间来完成，我们需要优先处理积分高且截止时间紧迫的任务。可以采用优先队列（最大堆）来实现，每次选择可完成任务中积分最高的任务进行处理。

参考代码

• Cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int N, T;
    cin >> N >> T;
    vector<pair<int, int>> tasks(N);
    for (int i = 0; i < N; i++) {
        cin >> tasks[i].first >> tasks[i].second;
    }
    sort(tasks.begin(), tasks.end());
    priority_queue<int> pq;
    int current_time = 0, score = 0;
    for (int i = 0; i < N; i++) {
        if (current_time < T && tasks[i].first > current_time) {
            pq.push(tasks[i].second);
            current_time++;
        } else if (!pq.empty() && pq.top() < tasks[i].second) {
            pq.pop();
            pq.push(tasks[i].second);
        }
    }
    while (!pq.empty()) {
        score += pq.top();
        pq.pop();
    }
    cout << score << endl;
    return 0;
}

• Python

import heapq

N, T = [int(input()) for _ in range(2)]
tasks = []
for _ in range(N):
    tasks.append(tuple(map(int, input().split())))
tasks.sort()
pq = []
current_time, score = 0, 0
for task in tasks:
    if current_time < T and task[0] > current_time:
        heapq.heappush(pq, -task[1])
        current_time += 1
    elif pq and -pq[0] < task[1]:
        heapq.heappop(pq)
        heapq.heappush(pq, -task[1])
while pq:
    score += -heapq.heappop(pq)
print(score)

• Java

import java.util.*;

public class TaskScheduler {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int T = scanner.nextInt();
        List<Task> tasks = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            tasks.add(new Task(start, end));
        }
        Collections.sort(tasks);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int currentTime = 0, score = 0;
        for (Task task : tasks) {
            if (currentTime < T && task.start > currentTime) {
                pq.add(task.end);
                currentTime++;
            } else if (!pq.isEmpty() && pq.peek() < task.end) {
                pq.poll();
                pq.add(task.end);
            }
        }
        while (!pq.isEmpty()) {
            score += pq.poll();
        }
        System.out.println(score);
    }

    static class Task implements Comparable<Task> {
        int start;
        int end;

        public Task(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Task other) {
            return Integer.compare(this.start, other.start);
        }
    }
}