优先队列及例题

  1. 例题

特性: 默认最大元素位于队首,所以出队时并非按照先进先出的原则进行.可以理解为排序后的队列.

1
2
3
4
5
priority_queue<vector<int>, less<int> > pq1;     // 使用递增less<int>函数对象排序

priority_queue<deque<int>, greater<int> > pq2;   // 使用递减greater<int>函数对象排序

其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。

声明方式:
1、普通方法:

1
2
3
priority_queue<int> q;                 //通过操作,按照元素从大到小的顺序出队

priority_queue<int,vector<int>, greater<int> > q;   //通过操作,按照元素从小到大的顺序出队

2、自定义优先级:

1
2
3
4
5
6
7
8
struct cmp {     
  operator bool ()(int x, int y)
  {
     return x > y;   // x小的优先级高 //也可以写成其他方式,如: return p[x] > p[y];表示p[i]小的优先级高
  }
};
priority_queue<int, vector<int>, cmp> q; //定义方法
//其中,第二个参数为容器类型。第三个参数为比较函数。

3、结构体声明方式:

1
2
3
4
5
6
7
8
9
10
11
struct node {     
  int x, y;
  friend bool operator < (node a, node b)
  {
    return a.x > b.x; //结构体中,x小的优先级高
  }
};
priority_queue<node>q; //定义方法
//在该结构中,y为值, x为优先级。
//通过自定义operator<操作符来比较元素中的优先级。
//在重载”<”时,最好不要重载”>”,可能会发生编译错误

例题

n个人一起排队接水,第i个人需要a[i]的时间来接水。
1 <= n <= 1000
1 <= a[i] <= 1000
同时只能有一个人接水,正在接水的人和没有接水的人都需要等待。
完成接水的人会立刻消失,不会继续等待。
你可以决定所有人接水的顺序,并希望最小化所有人等待时间的总和。

这个题我觉得可以排序,但是刚学了优先队列并且觉得很方便就用这个做.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;


struct cmp1{
bool operator ()(int &a,int &b){
return a < b;
}
};

int main(int argc, const char * argv[]) {
// priority_queue<int,vector<int>,greater<int>> que;
priority_queue<int,vector<int>,cmp1> que;
int n,t;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> t;
que.push(t);
}
int sum = 0;
while (!que.empty()) {
sum += que.top() * que.size();
que.pop();
}
cout << sum << endl;
return 0;
}
script>