备战蓝桥杯---数据结构与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;
}

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

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

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