洛谷 P3093 牛奶调度Milk Scheduling

https://www.luogu.org/problemnew/show/3093

思路

详见代码注释

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,maxn,now,ans;
struct poins
{
    int val,pos;
}l[];
bool operator < (poins a,poins b)
{
    return a.val<b.val;
} 
priority_queue<poins>q;
bool cmp(poins a,poins b)
{
    return a.pos>b.pos;
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%d%d",&l[i].val,&l[i].pos);
        maxn=max(maxn,l[i].pos);//记录最大截止时间 
    }
    sort(l+,l+n+,cmp);//时间从大到小排序 
    now=;
    for(int i=maxn;i>=;i--)
    {
        while(l[now].pos==i)//按截止时间从大到小加入,堆中元素一定合法 
        {
            q.push(l[now]);
            now++;
        }
        if(!q.empty()) 
        {
            ans+=q.top().val;//如果当前可以挤奶，就选择挤奶量最多的一头牛去挤奶
            q.pop();
        }
    }
    printf("%d",ans);
    return ;
}