旅游网站开发毕业设计,化妆品购物网站模板下载,高效简便的网站开发,wdcp配置网站反悔贪心
Work Scheduling G
什么是返回贪心呢#xff0c;就是先选择#xff0c;遇到更好的之后在反悔选择更好的#xff0c;这是符合贪心的逻辑的。
#include bits/stdc.h
// https://www.luogu.com.cn/problem/P2949
using namespace std;
struct node
{int d,…反悔贪心
Work Scheduling G
什么是返回贪心呢就是先选择遇到更好的之后在反悔选择更好的这是符合贪心的逻辑的。
#include bits/stdc.h
// https://www.luogu.com.cn/problem/P2949
using namespace std;
struct node
{int d, p;bool operator(node b){return d b.d;}
} w[100005];
long long ans;
priority_queueint, vectorint, greaterint q;
int main()
{int n;cin n;for (int i 1; i n; i){cin w[i].d w[i].p;}sort(w 1, w n 1); // 按照时间进行排序for (int i 1; i n; i){// 队列里面有几个q.size 就是最长的时间了// 如果和时间相等的话,把队列最前面的取出来进行比较if (w[i].d q.size()) // 这个如何理解呢如果w的d就是时间等于q的size{if (w[i].p q.top()){ans - q.top();q.pop();q.push(w[i].p);ans w[i].p;}}else{q.push(w[i].p);ans w[i].p;}}cout ans;
}代码的分析 首先分析题目在截止时间之前需要完成我们可以用struct结构体来存储对应的截止时间和价值根据截止时间进行排序。for循环遍历添加到队列中去如果要添加的截止时间等于优先队列的长度表示在这个时间内也可以做这件事情就需要判断即将添加进来的这件事情的价值和优先队列中的最小价值比较如果队列里面的最小价值小那么就将其出队再把新的添加进去。
