【ybt】【数据结构 二分堆 课过 例4】工作安排

本文主要是介绍【ybt】【数据结构 二分堆 课过 例4】工作安排，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

工作安排

题目链接：工作安排

---

题目描述

解题思路

我们先以时间为第一关键字、利润为第二关键字排序，然后贪心，在当前时间内选最大的利润。

code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;priority_queue<int> q;int n,m;
int ans;struct abc{int d,p;
}a[100010];bool cmp(abc a,abc b)
{if(a.d!=b.d)return a.d<b.d;return a.p>b.p;
}signed main()
{cin>>n;for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].d,&a[i].p),ans+=a[i].p;sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){q.push(-a[i].p);m++;if(m>a[i].d){ans+=q.top();q.pop();m--;}}cout<<ans<<endl;
}

这篇关于【ybt】【数据结构 二分堆 课过 例4】工作安排的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---