优先队列
又名二叉堆，分为最大堆和最小堆。插入元素后，队列中自动按照从小到大/从大到小排列，删除元素只能删除队首元素（最大/最小值）。C++中STL提供容器：priority_queue，其默认形式是最大堆，即从大到小排。
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
[NOIP2004]合并果子
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
直接用priority_queue做即可，不过由于默认是最大的在上面，存的时候可以存倒数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=300005,inf=0x7fffffff;
const double esp=1e-8;
int n,x,ans;//q[maxn];
priority_queue<int>q;
int main(){
cin>>n;
for(int i=1;i<=n;++i){
scanf("%d",&x);
q.push(-x);
}
for(int i=1;i<n;++i){
int t1=q.top(); q.pop();
int t2=q.top(); q.pop();
ans+=-t1-t2;
q.push(t1+t2);
}
cout<<ans;
return 0;
}
据说，要将堆的操作刻入自己的灵魂，就手打个板子。细节方面，注意pop中左右子树的大小问题：对于左右子树大小先移动指针，这样拆解编程复杂度，要不容易乱。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=300005,inf=0x7fffffff;
const double esp=1e-8;
int n,x,ans,cnt,q[maxn];
//priority_queue<int>q;
void push(int x){
cnt++; q[cnt]=x;
int i=cnt, j=cnt/2;
while(j!=0 && q[i]<q[j]){
swap(q[i],q[j]);
i=j; j/=2;
}
}
int top(){
return q[1];
}
void pop(){
q[1]=q[cnt]; cnt--;
int i=1,j=2;
if(j+1<=cnt&&q[j]>q[j+1]) j+=1;
while(j<=cnt&&q[j]<q[i]){
swap(q[i],q[j]);
i=j; j=i*2;
if(j+1<=cnt&&q[j]>q[j+1]) j+=1;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
scanf("%d",&x);
push(x);
}
for(int i=1;i<n;++i){
int t1=top(); pop();
int t2=top(); pop();
ans+=t1+t2;
push(t1+t2);
}
cout<<ans;
return 0;
}
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?
Running Median
对于这个问题，您将编写一个读取 32 位有符号整数序列的程序。在读取每个奇数索引值后，输出到目前为止接收到的元素的中值（中间值）
实际是一个对顶堆的维护问题。其实就是当加进一个数，当数比数小的那堆中最大的小，就加进数小的堆中，反之加进数大的堆中。
这里总结大根堆小根堆用STL容器维护的技巧：
priority_queue默认为大根堆，一种将其变为小根堆的方法为将目标数的倒数存入；还有一种就是传入比较函数，如：
priority_queue<int,vector<int>,greater<int> >：greater顾名思义，就是逐渐变大的意思，这里是小根堆；priority_queue<int,vector<int>,less<int> >：大根堆。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=300005,inf=0x7fffffff;
const double esp=1e-8;
int n,m,t,x;
priority_queue<int,vector<int>,greater<int> >bg;
priority_queue<int,vector<int>,less<int> >sm;
int main(){
cin>>t;
while(t--){
scanf("%d%d",&m,&n);
printf("%d %d\n",m,(n+1)>>1);
scanf("%d",&x);
printf("%d ",x);
sm.push(x);
for(int i=2;i<=n;++i){
scanf("%d",&x);
if(sm.top()>x) sm.push(x);
else bg.push(x);
if(sm.size()>bg.size()+1){
bg.push(sm.top());
sm.pop();
}else if(bg.size()>sm.size()+1){
sm.push(bg.top());
bg.pop();
}
if(bg.size()>sm.size()) printf("%d ",bg.top());
else if(sm.size()>bg.size()) printf("%d ",sm.top());
if(i%20==0) printf("\n");
}
while(!sm.empty()) sm.pop();
while(!bg.empty()) bg.pop();
printf("\n");
}
return 0;
}
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?
[JSOI2010]缓存交换
在计算机中，CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时，则需要从主存里把数据调入Cache。此时，如果Cache容量已满，则必须先从中删除一个。
例如，当前Cache容量为3，且已经有编号为10和20的主存单元。 此时，CPU访问编号为10的主存单元，Cache命中。 接着，CPU访问编号为21的主存单元，那么只需将该主存单元移入Cache中，造成一次缺失（Cache Miss）。 接着，CPU访问编号为31的主存单元，则必须从Cache中换出一块，才能将编号为31的主存单元移入Cache，假设我们移出了编号为10的主存单元。 接着，CPU再次访问编号为10的主存单元，则又引起了一次缺失。
对于一个固定容量的空Cache和连续的若干主存访问请求，聪聪想知道如何在每次Cache缺失时换出正确的主存单元，以达到最少的Cache缺失次数。
据说队列的问题常常伴随贪心出现，至少这道题是这样。实际上并不是出现次数越多越需要在内存中储存，如1 2 3 4 2 3 1 1 1 ，若cache最大容量为3，则先剔除1的方案实际上较好。正确的贪心是，把缓存区中元素中下一次出现最晚的那个给删除了。
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
const int maxn=300005,inf=0x7fffffff;
const double esp=1e-8;
int n,m,cnt,ans,a[maxn],nxt[maxn],jg[maxn];
priority_queue<int> q;
map<int,int> mp;
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=n;i>=1;--i){
if(mp[a[i]]==0) nxt[i]=100010; //mp[元素]=出现时刻
else nxt[i]=mp[a[i]]; //nxt[时刻]=该时刻元素的上一个出现的位置
mp[a[i]]=i; //更新a[i]出现的时刻
}
for(int i=1;i<=n;++i){
if(jg[i]==0){ //若当前元素没有在内存中
if(cnt<m){
cnt++; ans++;
jg[nxt[i]]=1;
q.push(nxt[i]);
} else{
jg[q.top()]=0;
q.pop();
ans++;
jg[nxt[i]]=1;
q.push(nxt[i]);
}
}else{
jg[nxt[i]]=1;
q.push(nxt[i]);
}
}
cout<<ans;
return 0;
}
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
tokitsukaze and Soldier
在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)
tokitsukaze想知道，团的战力最大为多少。
团队中的最小人数要求会对团队人数起直接限制作用，并作为最大团队人数的确定依据。维护一个按战力从大到小排的优先队列，我们可以先将数据中的战士按照可容纳人数从大到小排，然后不断加入队列。那多加的人怎么办呢？这个时候队列的作用就要大显身手了，只需要将队列顶部多余的人的战力从总战力中减去，同时弹出此人。总的战力再加上当前应加入的人的战力即可。那如果新加入的人战力非常小，还不如踢出的人的战力强怎么办呢？没关系，因为我们已将加入此人之前的战力记录过了，所以不会影响。
日常看了大佬的题解后觉得自己是个废物后痛定思痛自己又敲了一遍代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=100005,inf=0x3f3f3f3f;//inf设大了
const double esp=1e-8;
struct nd{
int v,s;
}d[maxn];
int n;
ll ans,sum;
priority_queue<int,vector<int>,greater<int> >q;
bool cmp(nd x,nd y){
return x.s>y.s;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)
scanf("%d%d",&d[i].v,&d[i].s);
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n;++i){
while(q.size()>=d[i].s){
sum-=q.top();
q.pop();
}
sum+=d[i].v;
q.push(d[i].v);
ans=max(ans,sum);
}
cout<<ans<<endl;
return 0;
}
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
[JSOI2007]建筑抢修
现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。
如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
我们从直觉上觉得应该先修ddl小的和耗时短的，但其实答案正是将两种思想结合的结果。
首先，我们肯定要抓紧时间修ddl短的，但考虑以下情况：a的ddl为10，耗时9；b的ddl为10，耗时为2，?此时我们只能选择一个进行抢修，选谁？答案当然是耗时短的b了。我们此时不知道是否还有别的建筑需要抢修，所以要尽量多地节省时间。这里就需要我们维护一个队列：耗时从大到小进行排列，如果要加入队列的抢修建筑的耗时小于队首，则抛除队首耗时长的任务，而将现在的建筑加入队伍。由于ddl较长且耗时较短，保证了加入队伍后不会超ddl。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=150005,inf=0x3f3f3f3f;
const double esp=1e-8;
struct nd{
ll t1,t2;
}d[maxn];
int n;
ll ans,sum,num;
priority_queue<ll,vector<ll>,less<ll> >q;
bool cmp(nd x,nd y){
return x.t2<y.t2;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i)
scanf("%lld%lld",&d[i].t1,&d[i].t2);
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n;++i){
if(sum+d[i].t1>d[i].t2){
if(d[i].t1<q.top()){
sum-=q.top();
q.pop();
num--;
}else continue;
}
sum+=d[i].t1;
q.push(d[i].t1);
num++;
ans=max(num,ans);
}
cout<<ans;
return 0;
}
有n个学生要打一场k分钟的比赛（当然要用电脑）。
每个学生的电脑有初始电量ai和每分钟耗电量bi（电量在这一分钟的最后一刻结算，即在下一分钟时才会减少，电量允许为负）。这样肯定是无法打完比赛的，所以学生们买了一个充电器，功率为任意值，每分钟可以使电量增加x，结算规则与耗电量一样，它可以在任一分钟给任一学生的电脑充电任意时长。
问题：求最小的x，使所有学生的电脑的电量在k分钟内都不为负。
首先必须为剩余持续时间最短的电脑充电，充完1分钟后就可以把它丢到以剩余时间从小到大排序的优先队列中，然后继续判断下一个要充电的电脑。
细节问题：在二分中，答案落在哪边，哪边就是备选答案区（如：if(jg(mid) r=mid-1，如果最后jg中判断答案所在区间为1，则最终答案输出r+1）；谁能想到我能因为卡常TLE这么久！（所以说一定要尽量使用scanf而不是cin）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
//scanf("%d",&);
using namespace std;
typedef long long ll;
const int maxn=200005,inf=0x3f3f3f3f;
const double esp=1e-8;
int n,k;
ll ans,sum,num;
struct nd{
double a,b,d;
bool operator <(const nd &x)const{
return x.d<d;
}
}a[maxn];
bool jg(ll x) {
priority_queue<nd>q;
for(int i=1; i<=n; ++i)
if(a[i].a/a[i].b<k)
q.push(a[i]);
if(q.empty()) return 0;
for(int i=1; i<=k; ++i) {
nd p=q.top();
q.pop();
if(p.d-i<-1)return 1;
p.d+=x*1.0/p.b;
q.push(p);
}
return 0;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%lf",&a[i].a);
for(int i=1;i<=n;++i){
scanf("%lf",&a[i].b);
a[i].d=a[i].a/a[i].b;
}
ll l=0,r=2e12;
while(l<=r){
ll mid=(l+r)>>1;
if(jg(mid)) l=mid+1;
else r=mid-1;//最终答案落在这里，所以用r+1
}
if(r>=2e12) cout<<-1;
else cout<<r+1;
return 0;
}
map/set
由二叉排序树实现（左子树所有元素<=根<=右子树所有元素），中序遍历即是排序结果。
例题：给出n个敌人的坐标，再给m个炸弹和爆炸方向，每个炸弹可以炸横排或竖排的敌人，问每个炸弹能炸死多少人。
这个时候就要巧用map了。若定义map<int,int>mx[size]，则mx[2]=3即可代表第二行第三列有敌人，与my[3]=2是等价的。而问题是我们第三行可能会有多个敌人，而map<int,multiset<int> >mx可以记录多组值，使得mx[2]={1,2,3}（第二行第一、二、三列有敌人），同时别忘了在my中删去相应的人以免以后重复计算。而若mx[3]={1,4,5}，要删除第3行的人，首先得到第三行有多少人;后通过迭代器在第三行中有值的序列中遍历（迭代器会依次指向1/4/5），后利用迭代器定位将my中对应x坐标的值擦除，最后将mx[3]clear掉。
这里总结几种用法：
1、map<int,multiset<int> >可以记录多组同一键值的数据，而不是一个键值唯一对应一个值
2、mx[pos].size()可以访问到键值所对应的长度，对应于每一行的人数
3、遍历map中key和value：
map<int,int>::iterator
for(it=mp.begin();it!=mp.end();it++){
?? ?cout<<it->first<<' '<<it->second<<endl;
}
4、遍历map数组（类比数组）中key和value：
#include<iostream>
#include<cstdio>
#include<map>
#include<set>
using namespace std;
int n,k,x,y;
map<int,multiset<int> >mp;
int main(){
mp[1].insert(1); mp[1].insert(5); mp[1].insert(7);
mp[2].insert(6); mp[2].insert(3);
map<int,multiset<int> >::iterator i;
multiset<int>::iterator j;
for(i=mp.begin();i!=mp.end();i++){
int pos=i->first;
for(j=mp[pos].begin();j!=mp[pos].end();j++)
cout<<pos<<' '<<*j<<endl;
// 访问key和value
}
return 0;
}
在验证擦除的时候，发现不知为啥不支持……等回来问问。
|