执行任务赚积分 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

现有 N 个任务需要处理，同一时间只能处理一个任务，处理每个任务所需要的时间固定为 1。

每个任务都有最晚处理时间限制和积分值，在最晚处理时间点之前处理完成任务才可获得对应的积分奖励。

可用于处理任务的时间有限，请问在有限的时间内，可获得的最多积分。

输入描述

第一行为一个数 N ，表示有 N 个任务（1 ≤ N ≤ 100 ）

第二行为一个数 T ，表示可用于处理任务的时间。（1 ≤ T ≤ 100）

接下来 N 行，每行两个空格分隔的整数（SLA 和 和 V ），SLA 表示任务的最晚处理时间，V 表示任务对应的积分。

1≤SLA≤100 , 0 ≤ V ≤ 100000

输出描述

可获得的最多积分

示例1

输入：
4
3
1 2
1 3
1 4
1 5

输出：
5

说明：
虽然有 3 个单位的时间用于处理任务，可是所有任务在时刻1之后都无效。 所以在第 1 个时间单位内，选择处理有 5 个积分的任务。1−3 时无任务处理。

示例2

输入：
4
3
1 2
1 3
1 4
3 5

输出：
9

说明：
第 1 个时间单位内，处理任务3，获得 4 个积分
第 2 个时间单位内，处理任务 4，获得 5 个积分
第 3 个时间单位内，无任务可处理。
共获得 9 个积分

题解

这道题是一个贪心算法的问题。以下是解题思路：

1. 将任务按照最晚处理时间（SLA）升序排序。
2. 使用一个最小堆（优先队列）来维护当前可选任务的积分值。
3. 遍历排序后的任务列表，将任务的积分值放入最小堆中，并累加总积分。
4. 在每一步中，判断优先队里中所有任务能否在（优先队列里中）任务最晚完成时间之内完成，完成不了则将积分值最小的任务删除掉同时维护总积分。
5. 最终的总积分即为答案

Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), t = scanner.nextInt();

        int[][] tasks = new int[n][2];
        for (int i = 0; i < n; i++) {
            tasks[i][0] = scanner.nextInt();
            tasks[i][1] = scanner.nextInt();
        }

        // 对任务进行排序（时间升序）
        Arrays.sort(tasks, Comparator.comparingInt(a -> a[0]));

        int result = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int[] task : tasks) {
            int last = task[0], v = task[1];
            minHeap.offer(v);
            result += v;

            // last 时间最多只能完成 last 个任务，任务无法在 last 时间内完成，则移除积分值最小值（最小堆）的任务
            // 可用于处理任务的时间 t 最多只能完成 t 个任务
            if (last < minHeap.size() || minHeap.size() > t) {
                result -= minHeap.poll();
            }
        }

        System.out.println(result);
    }
}

Python

import heapq


def fun():
    n = int(input())
    t = int(input())

    tasks = [tuple(map(int, input().split())) for _ in range(n)]
    # 对任务进行排序（时间升序）
    tasks.sort()

    h = []
    for last, v in tasks:
        heapq.heappush(h, v)

        # last 时间最多只能完成 last 个任务，任务无法在 last 时间内完成，则移除积分值最小值（最小堆）的任务
        # 可用于处理任务的时间 t 最多只能完成 t 个任务
        if last < len(h) or len(h) > t:
            heapq.heappop(h)

    print(sum(h))


if __name__ == "__main__":
    fun()

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

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());

    int result = 0;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (const pair<int, int>& task : tasks) {
        int last = task.first, v = task.second;
        minHeap.push(v);
        result += v;

        // last 时间最多只能完成 last 个任务，任务无法在 last 时间内完成，则移除积分值最小值（最小堆）的任务
        // 可用于处理任务的时间 t 最多只能完成 t 个任务
        while (last < minHeap.size() || minHeap.size() > t) {
            result -= minHeap.top();
            minHeap.pop();
        }
    }

    cout << result << endl;

    return 0;
}

相关练习题

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏