前提
原始堆
向其中插入数字3：先把3放到堆的最好，然后进行堆的大小颠倒。
插入堆的例子
堆的操作复杂度：
堆的两种操作所化的时间都和树的深度成正比。因此，如果一共有n个元素，那么每个操作可以在O（logn）的时间内完成。
堆的实现：
左儿子的编号是自己的编号X2+1；
右儿子的编号是自己的编号X2+2；
用数组便是二叉树时的编号
方法一
int heap[MAX_N],sz=0;
//上下不同层进行比较交换
void push(int x){
//i是自己节点的编号
int i=sz++;//因为是数组的原因，因该是下标+1
while(i>0){
//p为父亲节点的编号
int p=(i-1)/2;
//如果没有大小颠倒则退出
if(heap[p]<=x) break;
//把父亲节点的数值放下来，而把自己提上去
heap[i]=heap[p];
i=p;
}
heap[p]=x;
}
方法二
//不同一层进行比较交换
int pop(){
//最小值
int ret=heap[0];
//要提到根的数值
int x=heap[--sz];
//从根开始向下交换
int i=0;
while(i*2+1<sz){
//比较儿子的值
int a=i*2+1,b=i*2+2;
if(b<sz&&heap[b]<heap[a])
a=b;
//如果没有大小颠倒则退出
if(heap[a]>=x) break;
//把儿子的数值提上来
heap[i]=heap[a];
i=a;
}
heap[i]=x;
return ret;
}
优先队列
STL中的priority_queue取出数值时得到的是最大值
#include <bits/stdc++.h>
using namespace std;
int main(){
//声明
priority_queue<int> pque;
pque.push(3);
pque.push(5);
pque.push(1);
//不断循环到空为止
while(!pque.empty()){
//获取并删除最大值
printf("%d\n",pque.top());
pque.pop();
}
return 0;
}
title
样例
代码
#include <bits/stdc++.h>
using namespace std;
int N,L,P,A[1000001],B[101];
void solve(){
A[N]=L;
B[N]=0;
N++;
//维护加油站的优先队列
priority_queue<int> que;
//ans:加油次数 ，pos:现在所在位置 ，tank:油箱中汽油的量
int ans=0,pos=0,tank=P;
for(int i=0;i<N;i++){
//接下来是要前进的距离；
int d=A[i]-pos;
//不断加油直到油量足够行驶到下一个加油站
while(tank-d<0){
if(que.empty()){
printf("-1");
return;
}
tank+=que.top();
que.pop();
ans++;
}
tank-=d;//加油加够后的一段路程用油箱里的油
pos=A[i];
que.push(B[i]); //这个才是加油站加油
}
printf("%d\n",ans);
}
int main(){
cin>>N>>L>>P;
for(int i=0;i<N;i++)
scanf("%d",&A[i]);
for(int i=0;i<N;i++)
scanf("%d",&B[i]);
solve();
}
Expedition
最近因为期末的原因有点小久没有看白书了//我对不起你~LXY说软院也要有ACM训练营了加油！
这道题是一步一步入坑，然后在一步一步地走出来的
1.没想到会用贪心，然后就直接打了，emmm~runtime error
2.用了贪心后，排序那里应该是从大到小，从与终点town离得最远的开始
3.leng[N].A=0;不是等于L；因为之后还要用L-0；
Code
//#include<bits/stdc++.h>
using namespace std;
int N,L,P;
struct len{
int A,B;
}leng[10001];
bool cmp(len l1,len l2){
return l1.A>l2.A;
}
int main(){
freopen("data","r",stdin);
cin>>N;
for(int i=0;i<N;i++){
cin>>leng[i].A>>leng[i].B;//A为距离B为可用的燃料量
}
cin>>L>>P;//L为全长，P为初始的燃料数
priority_queue<int> que;
leng[N].A=0;
leng[N].B=0;
N++;
sort(leng,leng+N,cmp);
int ans=0,pos=0,tank=P;
for(int i=0;i<N;i++){
int d=L-leng[i].A-pos;//先求出距离叭
while(tank-d<0){
if(que.empty()){
cout<<"-1"<<endl;
return 0;
}
tank+=que.top();
que.pop();
ans++;
}
tank-=d;
pos=L-leng[i].A;
que.push(leng[i].B);
}
cout<<ans<<endl;
return 0;
}
Fence Repair
学会了优先队列的方法后，我现在立刻马上right now收回在哈夫曼编码中说的某些话
用优先队列快了很多。
Code
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int L[50001],N;
int main(){
cin>>N;
for(int i=0;i<N;i++)
cin>>L[i];
ll ans=0;
//声明一个从小到大取出数值的优先队列
priority_queue<int,vector<int>,greater<int> > que;
for(int i=0;i<N;i++)
que.push(L[i]);
//循环到只剩下一块木板为止
while(que.size()>1){
//取出最短板和次短板
int l1,l2;
l1=que.top();
que.pop();
l2=que.top();
que.pop();
//两块木板合并
ans+=l1+l2;
que.push(l1+l2);
}
cout<<ans;
return 0;
}
网友评论