单选题 适中
#19822

给定有 个任务,每个任务有截止时间和利润,每个任务耗时 1 个时间单位、必须在截止时间前完成,且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润,可以…

给定有 个任务,每个任务有截止时间和利润,每个任务耗时 1 个时间单位、必须在截止时间前完成,且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润,可以采用贪心策略,即按利润从高到低排序,尽量安排,则横线处应填写( )。

struct Task { 
    int deadline; //截止时间 
    int profit; //利润 
}; 
void sortByProfit(vector<Task>& tasks) { 
    sort(tasks.begin(), tasks.end(), 
        [](const Task& a, const Task& b) { 
            return a.profit > b.profit; 
        }); 
} 
int maxProfit(vector<Task>& tasks) { 
    sortByProfit(tasks); 
    int maxTime = 0; 
    for (auto& t : tasks) { 
        maxTime = max(maxTime, t.deadline); 
    } 
    vector<bool> slot(maxTime + 1, false); 
    int totalProfit = 0; 
    for (auto& task : tasks) { 
        for (int t = task.deadline; t >= 1; t--) { 
            if (!slot[t]) { 
                _______________________ //在此处填入代码 
                break; 
            } 
        } 
    } 
    return totalProfit; 
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析
首先按利润降序排列任务。确定最大截止时间以初始化时间槽数组,每个槽位标记是否被占用。遍历已排序的任务,对每个任务从其截止时间向前查找第一个空闲时间槽。若找到空闲槽位,则将其标记为占用,并将该任务的利润累加到总利润中。遍历所有任务后,返回累计的总利润。