备战蓝桥杯---数据结构与STL应用（入门4）

本专题主要是关于利用优先队列解决贪心选择上的“反悔”问题

话不多说，直接看题：

下面为分析：

很显然，我们在整体上以s[i]为基准，先把士兵按s[i]排好。然后，我们先求s[i]大的开始，即规定选人数不超过s[i]的士兵，下面为图解：

下面为AC代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long v,s;
}a[1000100];
long long n;
bool cmp(node a,node b){
    return a.s>b.s;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i].v,&a[i].s);
    }
    sort(a+1,a+1+n,cmp);
    priority_queue<long long,vector<long long>,greater<long long> > q;
    long long cap=a[1].s,sum=a[1].v,max1=-1;
    q.push(a[1].v);
    for(int i=2;i<=n;i++){
      if(a[i].s==cap){
            q.push(a[i].v);
            sum+=a[i].v;
         if(q.size()>cap){
             sum-=q.top();
             q.pop();
         }
        }  
        else{
            cap=a[i].s;
            q.push(a[i].v);
            sum+=a[i].v;
            while(q.size()>cap){
                sum-=q.top();
                q.pop();
            }
        }
        max1=max(max1,sum);
    }
    cout<<max1;
}

再来一道类似的：

下面为分析：

类似的，我们指定一个基准，我们按deadline升序排好，从小的开始枚举。

如果前面的时间加当前所需没超当前建筑的deadline，我们就添加。

否则，我们用它与前面所需时间max的比，如果比他小就替换。

下面为AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
    int t1,t2;
}a[150010];
bool cmp(node a,node b){
    return a.t2<b.t2;}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].t1,&a[i].t2);
    sort(a+1,a+n+1,cmp);
    priority_queue<int> q;
    int dead=-1,cnt=0,sum=0;
    for(int i=1;i<=n;i++){
        q.push(a[i].t1);
        cnt++;
        sum+=a[i].t1;
        if(a[i].t2!=dead) dead=a[i].t2;
        if(sum>dead){
                sum-=q.top();
                cnt--;
                q.pop();
            }  
        }
    cout<<cnt;
}

让我们总结一下，本专题围绕利用优先队列解决贪心选择上的“反悔”（或优化）问题（常用于固定枚举一个基准值）

最后，举个形象的例子：我们的成长就是从一开始的幼稚不断地经历岁月的打磨，见识的增长，不断优化，最终走向成熟。

希望可以和大家一起继续前行！