本专题主要是关于利用优先队列解决贪心选择上的“反悔”问题
话不多说,直接看题:
下面为分析:
很显然,我们在整体上以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;
}
让我们总结一下,本专题围绕利用优先队列解决贪心选择上的“反悔”(或优化)问题(常用于固定枚举一个基准值)
最后,举个形象的例子:我们的成长就是从一开始的幼稚不断地经历岁月的打磨,见识的增长,不断优化,最终走向成熟。