Work-Scheduling
题目链接
Work-Scheduling
思路
时间从前往后贪心，创建一个堆，堆的大小就是当前选择的最远时刻，所以每此比较t和堆的大小。
1.t>q.size()时，直接入堆
2.t<q.size()时, 时间已经过了，这份工作无效了
3.t==q.size()时，判断当前工作是否值得，值得的话，进堆，然后把贡献最小的出堆。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+10;
struct node
{
int time,cost;
}a[maxn];
int cmp(node a,node b)
{
return a.time<b.time;
}
priority_queue<ll,vector<ll>,greater<ll> >q;
set<int>s;
int main()
{
int n;
scanf("%d",&n);
ll ans = 0;
for(int i=0;i<n;i++)
{ int x,y;
scanf("%d %d",&a[i].time,&a[i].cost);
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
{
if(a[i].time<q.size())continue;
else if(a[i].time==q.size())
{
if(a[i].cost>q.top())
{
ans-=q.top();q.pop();
q.push(a[i].cost);
ans+=a[i].cost;
}
}
else ans+=a[i].cost,q.push(a[i].cost);
}
cout<<ans<<endl;
}
|