华为4.13机考第二题个人反思

笔者昨天做了华为4.13的机考，考试的时候第二题的思路错了导致测例只过了10%，考完以后自己给出了测例证明自己做法错了，并在此基础上设计了一种解法，笔者水平有限，如有错误欢迎指正。

代码如下，总体思路为先进行自定义排序，将截止时间久的任务排在前面，截止时间一样时，积分高的排在前面;之后遍历每个时间节点，进行任务选择，具体选择算法如下： 从最后一天开始遍历至第一天，同时内层从排序后的第一个任务开始遍历任务，并用一个优先队列储存当前时间节点下允许完成的任务。因把截止时间久且未被选中的任务存起来，看看与前面的任务相比是否有更高的性价比，且这些任务在之后遍历到的更早的截至时间下完成都是有积分的。

1.若当前任务队列为空且当前遍历到的任务截止时间小于当前时间节点，无事发生;

2.若当前任务队列为空且当前遍历到的任务截止时间大于等于当前时间节点，加上当前任务的得分，且将后续与当前任务截止时间一样的任务插入优先队列，任务游标移动到非当前时间节点的一个任务处或者数组尾部;

3.若当前任务队列不为空且当前遍历到的任务截止时间小于当前时间节点，那么此刻我们完全没必要去做内层遍历到的任务，做了也没积分，所以从任务队列里挑一个任务完成并获取积分;

4.若当前任务队列不为空且当前遍历到的任务截止时间大于等于当前时间节点，那么比较任务队列队首的任务与当前遍历到的任务的积分，做较高的那个，如果做的是遍历到的任务，那么其无需插入任务队列，但是后续与当前任务截止时间一样的任务插入优先队列，如果做的是任务队列中的任务，那么遍历到的任务也要插入任务队列。

任务队列可以优化成一个单调队列(笔者不太了解这种数据结构)?因为遍历的时间结点有限，所以当任务包中的长度大于剩余可遍历时间结点数时，需要弹出积分最低的任务。

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


int main() {
    vector<pair<int,int>> nums = {
            {1,1}, {2,10}, {2,11}
    };
    auto f = [](pair<int,int>& a, pair<int,int>& b){
        if(a.first != b.first) return a.first > b.first;
        else return a.second > b.second;
    };
    sort(nums.begin(),nums.end(),f);
    priority_queue<int,vector<int>, greater<int>>q;
    int maxTime = nums[0].first;
    int ans = 0, id = 0;
    int len = nums.size();
    for(int t = maxTime; t >= 1; t--){
        if(id >= len) break;
        if(q.empty()){
            if(nums[id].first >= t){
                ans += nums[id++].second;
                while(id < len && nums[id].first == t) q.push(nums[id++].second);
            }
            else continue;
        }
        else{
            if(nums[id].first >= t){
                if(q.top() > nums[id].second){
                    ans += q.top();
                    q.pop();
                    while(id < len && nums[id].first == t) q.push(nums[id++].second);
                }
                else if(q.top() <= nums[id].second){
                    ans += nums[id++].second;
                    while(id < len && nums[id].first == t) q.push(nums[id++].second);
                }
            }
            else{
                ans += q.top();
                q.pop();
            }
        }
    }
    cout << ans << endl;
    return 0;
}