写了几道题,发现优先队列的题和贪心关系还挺密切

下面两道题都是在贪心,用优先队列来辅助判断是不是有更好的选择,然后后悔原来的元素,选择更好的元素

题解51:https://ac.nowcoder.com/acm/problem/50439 tokitsukaze and Soldier

因为待会能后悔,所以按照要求的高低排序.先选要求高的,待会交换的时候,要求低的总是能交换(相当于减少了一个变量),然后优先去除当前战力最低的,加入新的战士,随后仅用考虑交换后是不是战力更高

AC代码&思路:

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
using ll=long long;
struct ty
{
    int v,s;//v战力,s人数
}sol[100010];
priority_queue<int,vector<int>, greater<int> > pri;//要求战力低的排队首,方便pop()
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i) {cin>>sol[i].v>>sol[i].s;}
    sort(sol+1,sol+1+n, [](const ty &a, const ty &b) {return a.s>b.s;});//要求高的排前面
    ll ans=0,tmp=0;//tmp记录每一次交换后的总战力值,ans在这些总战力值中找到最大的
    for(int i=1;i<=n;++i)
    {
      //先把提高最大人数后满足要求的人全部加进来,等下人多了,再把战力少的人扔出去
        tmp+=sol[i].v;
        pri.push(sol[i].v);
        while(pri.size()>sol[i].s)//sol[i].s是当前要求最低的,要优先满足他的要求,因为s不一定连续,所以用while
        {
          //人多,把优先队列队首pop()
            tmp-=pri.top();
            pri.pop();
        }
        ans=max(ans,tmp);
    }
    cout<<ans;
    return 0;
}

题解52:https://ac.nowcoder.com/acm/problem/20154 [JSOI2007]建筑抢修

这一题还是按照要求从高到低排序,因为要求高(deadline靠前)的不一定能接受要求低(deadline靠后)的建筑的要求,所以不能后悔,反之则可以后悔

后悔时,优先后悔耗时 长的

AC代码&思路:

#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
using ll  =long long;
struct ty
{
    int need,dead;   
}a[150010];
priority_queue<int> pri;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i) {cin>>a[i].need>>a[i].dead;}
    sort(a+1,a+1+n, [](const ty &a, const ty &b) {return a.dead<b.dead;});
    ll curtime=0;//前面一共花的时间
    int cnt=0;//修好的建筑数
    for(int i=1;i<=n;++i)
    {
        if(curtime+a[i].need<=a[i].dead) {++cnt;curtime+=a[i].need;pri.push(a[i].need);}//如果能修完当前建筑,就"暂时"把它加到"修理清单"中
      //进入下面这个if的前提是curtime+a[i].need>a[i].dead,耗的时间超过了
        else if(a[i].need<pri.top())//为什么不用不像题解51一样用while?因为题解51要求的是总战力最多,跟总人数没关系.而这里相当于要求总修理数(题目的求解对象)最多.如果把耗时少有deadline大的修理建筑放到前面去,无论怎么样都不会不成功,所以不用用while一直判断,而且这里是一换一,如果一直换下去,没有那么多同样好的建筑供你换
        {
            curtime+=(a[i].need-pri.top());//即-pri.top(),+a[i].need
            pri.pop();//--cnt
            pri.push(a[i].need);//++cnt,和前面的--cnt抵消了
        }
    }
    cout<<cnt;
    return 0;
}