前提

原始堆

向其中插入数字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;
}