[贪心]合并果子——落谷-P1090

优先队列

  优先队列中元素具有优先级，在删除时删除优先级高的元素。优先队列本质上还是队列，元素增添在队尾，取元素时取队首元素，在优先队列中只不过变成了取优先级最高的元素。优先队列内部排序的方式是堆排序，升序的优先队列就相当于一个小根堆。
头文件#include <queue>
升序队列priority_queue<int, vector<int>, greater<int> >， 其中greater<int>是STL中的结构体，表示数据从小到大进行输出。
降序队列priority_queue<int, vector<int>, less<int> >,其中less<int>是内置数据从数据从大到小进行输出。

思路

  分析题目可以知道每次取最小的两堆的果子，可以使得总花销最小，因此，使用优先队列存放果子的数量后，只需要每次从头取出两个值进行相加，这就是这一次合并的代价，从队列中删掉这两个值，因为已经搬运过了。再把合并好的存到队列中，供下次搬运，直到队列为空，也就是所有的果子都搬运完了。

AC代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int , vector<int>, greater<int> > p;
int n;
int ans = 0;

int main(){
    cin >> n;
    int temp;
    for(int i = 0; i < n; i++){
        cin >> temp;
        p.push(temp);       
    }
    //一次要合并两堆，当队列中只剩下两堆时，下一次操作就可以把所有的果子合并完
    while(p.size() >= 2){
        int a = p.top();
        p.pop();//删除一堆果子
        int b = p.top();
        p.pop();//删除另一堆果子
        int sum = a+b;
        ans += sum;
        p.push(sum);//将合并好的新果子放回到队列中
    }
    cout << ans << endl;
    return 0;
}

STL结构体排序的代码

greater<int>

template<class _Ty = void>
    struct less
    {    // functor for operator<
    typedef _Ty first_argument_type;
    typedef _Ty second_argument_type;
    typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {    // apply operator< to operands
        return (_Left < _Right);
        }
    };

less<int>

template<class _Ty = void>
    struct greater
    {    // functor for operator>
    typedef _Ty first_argument_type;
    typedef _Ty second_argument_type;
    typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {    // apply operator> to operands
        return (_Left > _Right);
        }
    };

自定义排序

struct Node{
    int x,y;
    Node(int a=0, int b=0):
        x(a), y(b) {}
};

struct cmp{
    bool operator()(Node a, Node b){
        if(a.x == b.x)  return a.y>b.y;
        return a.x>b.x;
    }
};

priority_queue<Node,vector<Node>,cmp>q;