【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【贪心+优先队列】2023C-在规定时间内获得的最大报酬【欧弟算法】全网注释最详细分类最全的华为OD真题题解

���LeetCode算法/华为OD考试扣扣交流群可加 948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

• 题目描述与示例
• • 题目描述
  • 输入描述
  • 输出描述
  • 示例一
  • • 输入
    • 输出
    • 说明
    • 示例二
    • • 输入
      • 输出
      • 说明
      • 示例三
      • • 输入
        • 输出
        • 解题思路
        • 代码
        • • Python
          • Java
          • C++
          • 时空复杂度
          • 华为OD算法/大厂面试高频题算法练习冲刺训练

            题目描述与示例

            题目描述

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

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

            可用于处理任务的时间有限，请问在有限的时间内，可获得的最多报酬?

            1  
            输入描述
             
            第一行输入两个数T和N，表示N个任务和全部任务的最迟的时间节点T。
             
            接下来输入N行，每一行输入两个数K和L表示一个任务，K为这个任务的最晚完成时间，L为完成该任务能够获得的报酬。
             
            输出描述
             
            一个整数，表示能够获取的最大报酬。
             
            示例一
             
            输入
             
            3 41 21 31 42 5
             
            输出
             
            9
             
            说明
             
            在单位时间1，完成任务2，获得报酬4
             
            在单位时间2，完成任务3，获得报酬5
             
            示例二
             
            输入
             
            3 51 32 23 13 44 5
             
            输出
             
            12
             
            说明
             
            在单位时间1，完成任务0，（最晚完成时间是1），获得报酬3
             
            在单位时间2，完成任务4，（最晚完成时间是4），获得报酬5
             
            在单位时间3，完成任务3，（最晚完成时间是3），获得报酬4
             
            示例三
             
            输入
             
            2 31 22 51 5
             
            输出
             
            10
             
            解题思路
             
            本题的陷阱在于，每一个任务给定的时间K是最晚完成时间，这意味该任务可以在小于等于K的任意一个时刻完成。
             
            譬如对于示例二
             

            • 在单位时间1，第0-4个任务都是可以选择去完成的任务。
            • 在单位时间2，第1-4个任务都是可以选择去完成的任务。
            • 在单位时间3，第2-4个任务都是可以选择去完成的任务。

              如果意识到了这一点，那么以下结论是显而易见的：随着时间增大，某些任务已经错过了其对应的最晚完成时间K，那么可以选择的任务是变得越来越少的。

              难点在于，在当前时间较小的时候，如果我们面临多个选择，我们无法确定应该选择哪个任务。因为我们在做选择时存在两个不同的维度需要考虑：

              1. 该任务的报酬L尽可能地大
              2. 该任务的最晚完成时间K尽可能地小

              如果正向地考虑时间变化，我们没有办法同时保持上述两个维度都满足最优的条件。换句话说，没有办法贪心地从局部最优得到全局最优解。

              考虑一种特殊情况，假设仅存在一个任务i的最晚完成时间K大于等于总体最晚完成时间T，那么在时刻T时，只有这一个任务i可以被选择。即使这个任务i有可能可以在更早完成，我们也希望把它拖到时刻T来完成，这样才能让时刻T之前的单位时间去完成其他任务。

              以示例三为例，对于时刻t = 2，仅存在工作1的最晚完成时间是K = 2，那么工作1我们一定希望把它放在t = 2来完成而不是放在t = 1来完成，因为这样才能在t = 1时刻，去完成更多任务。

              所以贪心策略应该是从后往前考虑时间变化。即时刻t从T递减变化到1。

              • 考虑某一个时刻t，假设该时刻有m个可以选择的任务，那么我们会在里面挑出报酬最大的那个任务去完成。
              • 在时刻t-1，除了剩下的m-1个任务，还有最晚完成时间K = t-1的若干个任务（假设数量为p）需要放在一起考虑，那么此时一共有p+m-1个任务需要考虑，同样在里面挑出报酬最大的那个任务去完成。

                for t in range(T, 0, -1):    cur_task_lst += dic_task_last_t[t]    cur_task_lst.sort()    if len(cur_task_lst) > 0:        ans += cur_task_lst.pop()

                其中dic_task_last_t为一个哈希表，储存了最晚完成时间为时刻t的任务的报酬。其

                • key为时刻t
                • value为由最晚完成时间为t的任务的报酬所构成的列表

                  注意：上述挑选单个时刻里最大值的过程，更好的方法是用一个最大容量为T的优先队列/堆来维护，这样单个时刻挑选最大值的复杂度可以降为O(logT)。但因为数据量很小，所以直接排序也是可以通过的。感兴趣的同学可以尝试用优先队列的方法来维护上述过程。

                  代码

                  Python

                  # 题目：【贪心】2023C-在规定时间内获得的最大报酬# 分值：100# 作者：闭着眼睛学数理化# 算法：贪心# 代码看不懂的地方，请直接在群上提问from collections import defaultdict# 用一个哈希表储存最晚完成时间为时刻t的任务的报酬# key为时刻t# value为由最晚完成时间为t的任务的报酬所构成的列表dic_task_last_t = defaultdict(list)# 输入总体最晚完成时间T，任务个数NT, N = map(int, input().split())# 循环N次，输入每一行for _ in range(N):    # 输入最晚完成时间K，完成该任务获得的报酬L    K, L = map(int, input().split())    # 如果K大于T，那么该任务最晚是在时刻T完成    # 如果K小于T，那么该任务最晚是在时刻K完成    # 因此键需要取两者之间的较小值    dic_task_last_t[min(K, T)].append(L)ans = 0# 在时刻t时，可以选择的任务的报酬构成的列表，一开始为空列表cur_task_lst = list()# 逆向遍历从T到1的所有时刻tfor t in range(T, 0, -1):    # t时刻可以完成的任务的报酬储存在dic_task_last_t[t]中    # 将其更新入cur_tack_lst中    cur_task_lst += dic_task_last_t[t]    # 对cur_task_lst进行排序    cur_task_lst.sort()    # 如果此时cur_task_lst不为空，则选择其中报酬最大的任务去完成    # 即删除cur_task_lst末尾元素，并将该元素更新入ans中    if len(cur_task_lst) > 0:        ans += cur_task_lst.pop()print(ans)

                  Java

                  import java.util.*;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int T = scanner.nextInt(); // 总体最晚完成时间        int N = scanner.nextInt(); // 任务个数        Map dic_task_last_t = new HashMap();        for (int i = 0; i  new ArrayList()).add(L);        }        int ans = 0;        List curTaskList = new ArrayList();        for (int t = T; t > 0; t--) {            List taskList = dic_task_last_t.getOrDefault(t, new ArrayList());            curTaskList.addAll(taskList);            Collections.sort(curTaskList);            if (!curTaskList.isEmpty()) {                int maxReward = curTaskList.remove(curTaskList.size() - 1);                ans += maxReward;            }        }        System.out.println(ans);    }}

                  C++

                  #include #include #include #include using namespace std;int main() {    int T, N;    cin >> T >> N;    unordered_map dic_task_last_t;    for (int i = 0; i > K >> L;        int t = min(K, T);        dic_task_last_t[t].push_back(L);    }    int ans = 0;    vector curTaskList;    for (int t = T; t > 0; t--) {        vector taskList = dic_task_last_t[t];        curTaskList.insert(curTaskList.end(), taskList.begin(), taskList.end());        sort(curTaskList.begin(), curTaskList.end());        if (!curTaskList.empty()) {            int maxReward = curTaskList.back();            curTaskList.pop_back();            ans += maxReward;        }    }    cout