dequeue双向队列dequeueintque； //双向队列que.push_front(//队列前填充元素que.push_back )//队列后填充元素que.pop_front )//队列中的第一个元素que.pop_back
构想1:秘技dequeue(STL赛高！ ）
下面，根据雨的巨大生动形象的例子，进行简单说明。
题意：展示各期宏碁的实力。 众所周知，大学基本上是4年，所以滑动窗口的大小是4。 各窗口中实力最强最弱的是多少？
举个例子，1 4 6 3 3 3 2
现在求最大值，最小值根据最大值变更就可以了。
首先，让我们看看1在排队。 (我是dequeue。 省略详细说明。 )未达到4个要素，因此不输出。 另外，到第二个要素4为止，大于1，说明4的伟大作用，使1废弃了。 也就是说，“去尾巴”的话，得到队列4。 再变成6、6、4，所以在6的存在下，4被废弃，被扔出去，得到队列6。 另外，3、3小于6，说明他有机会。 因为可以等待6月的退役。 (也就是说，6从窗口出来)，他可能是最大的。 按3得到6，3的矩阵，现在已经到了窗口的大小，所以输出队伍的开头6，看3，按等于列末尾的元素，输出另一个6，按下接下来的3之后，我们
总之，实现单调队列主要分为四个部分：
去尾：队尾元素出队列.当新的acmer等待加入团队时，需要从团队的末尾判断是否破坏团队的单调性，如果可能的话，最后走。 3358 www.Sina.com/http://www.Sina.com/.必须在acmer满4年后退役。 也就是说，从队列中删除http://www.Sina.com/# include cstdio # include cstring # include string # include cmath # iostream # includeded include stdlib.h # includes stream # include map # includesetusingnamespacestd； # define INF0x 3f 3f 3f # definemax 1000005 typedeflonglongll； inline int IntRead () {//int的速读char ch=getchar )； int s=0，w=1； wile(ch(0)|ch (9) ) if ) ch=='-' ) w=-1； ch=getchar (； }while(ch='0'ch='9' ) { s=s * 10 ch - '0)； ch=getchar (； }返回s * w； (}int tr[MAX]； int main () { int n，k； dequeintq； //双向队列cinnk； for(intI=1； i=n； I ) tr[i]=IntRead (； for(intI=1； i=n； I () { while (！ q.empty(tr[I]tr[q.back ) { q.pop_back )； //走到末尾}q.push_back(I )； //入队if(I=k ) )//从第k个开始，必须在后面输出while (！ q.empty(I-q.front ) ) { q.pop_front； //摘下头}if(I==k ) couttr[q.front； 控制//空间输出的elsecout''tr[q.front(]； } } coutendl； q.clear (； //清空队列for (inti=1； i=n； I
+){ while (!q.empty() && tr[q.back()] < tr[i]) { q.pop_back(); } q.push_back(i); if(i >= k){ while (!q.empty() && i - q.front() + 1 > k) { q.pop_front(); } if(i == k) cout<<tr[q.front()]; else cout<<' '<<tr[q.front()]; } } cout<<endl;} 思路2:手写队列
head代表队列头，tail代表队列尾
结构体的q数组即为“双向队列”，其id用来记录下标，val来记录值
还是那四步，去尾入队去头取解。
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <vector>#include <stack>#include <queue>#include <stdlib.h>#include <sstream>#include <map>#include <set>using namespace std;#define inf 0x3f3f3f3f#define MAX 1000000 + 5typedef long long ll ;inline int IntRead(){//int的快读 char ch = getchar(); int s = 0, w = 1; while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar();} return s * w;}int tr[MAX], n, k;struct ran{ int id, val;}q[MAX];void getmin(){ int head = 1, tail = 0;//初始化 for(int i = 1; i <= n; ++i){ while (head <= tail && tr[i] < q[tail].val) tail--;//去尾 q[++tail].id = i;//入队的时候记得要记录两部分 q[tail].val = tr[i]; while (i - q[head].id + 1 > k) head++;//去头 if(i >= k){ if(i == k)cout<<q[head].val;//控制空格，防止PE else cout<<' '<<q[head].val; } } cout<<endl;}void getmax(){ int head = 1, tail = 0; for(int i = 1; i <= n; ++i){ while (head <= tail && q[tail].val < tr[i]) tail--; q[++tail].id = i; q[tail].val = tr[i]; while (i - q[head].id + 1 > k) head++; if(i >= k){ if(i == k)cout<<q[head].val; else cout<<' '<<q[head].val; } } cout<<'n';}int main(){ cin>>n>>k; for(int i = 1; i <= n; ++i) tr[i] = IntRead(); getmin(); getmax(); return 0;}我看了一下这两个的时间差的不多，2ms，我感觉还是dequeue好写一些，嘎嘎，感觉写成函数更美观一点哎=(.)=
优先队列 合并果子 题意：n个果子，数目为tr[i]，进行n - 1次合并操作，每次都消耗两堆果子的重量和的体力，耗费的总体力等于每次合并所耗费的体力和，求最小值
思路1:使用秘技STL，priority_queue来操作，但这个优先队列是从大到小的，有一个非常非常非常简便的方法来改变其顺序——加负号！！！
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <vector>#include <stack>#include <queue>#include <stdlib.h>#include <sstream>#include <map>#include <set>using namespace std;#define inf 0x3f3f3f3f#define MAX 1000000 + 5typedef long long ll ;priority_queue<int>q;int main(){ int n, m; cin>>n; for(int i = 1; i <= n; ++i){ cin>>m; q.push(-m); } ll ans = 0; for(int i = 1; i < n; ++i){ int x = -q.top(); q.pop(); int y = -q.top(); q.pop(); ans += x + y; q.push(-x - y); } cout<<ans<<endl; return 0;} 思路2:手撕优先队列。
首先我们要知道优先队列其实是一种堆，是一棵完全二叉树，而这个二叉树又满足一个规律——任意节点都小于（或大于）其子节点
这个题我们要用到插入，弹出，取顶三个操作
插入：对于一个新的数插进来，我们不能坏了优先队列的顺序，所以就插在最后，然后和他的父节点进行比较，看看需不需要交换，一直换下去
弹出：对于弹出的数是队首，也就是这里面最小的（或者最大的数），所以可以直接把最后一个元素拿过来替代他，然后再和他的子节点比较，这里会出问题，因为上次是和父节点比较（众所周知，你只有一个爹，但爱撒娇的大船不一定只有你一个孩子，是不是很形象o(≧v≦)o），只有一个父节点，而现在和子节点比较，对于升序的优先队列，我们得取小的子节点与父节点交换
取顶：就直接取q[1]即可
注意一些边界条件
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <vector>#include <stack>#include <queue>#include <stdlib.h>#include <sstream>#include <map>#include <set>using namespace std;#define inf 0x3f3f3f3f#define MAX 1000000 + 5typedef long long ll ;inline int IntRead(){ char ch = getchar(); int s = 0, w = 1; while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * w;}int n,q[MAX],tot, ans;void push(int x){//塞新的数进去 q[++tot] = x; int i = tot, j = i / 2;//i是子节点，j是父节点 while (j > 0 && q[j] > q[i]) {//没有出界且父亲节点的值大于子节点的值就交换 swap(q[i], q[j]); i=j;j=i/2;//原来的父亲节点就成了现在的子节点，而现在的子节点是父节点除以2所得 }}int top(){//取顶 return q[1];}void pop(){//弹出队首 q[1] = q[tot]; tot--; int i = 1, j = 2 * i;//i是父节点，j是子节点//可能i的另一个子节点k比j小，此时就是换i和k，所以要判断一下谁更小 if (j + 1 <= tot && q[j] > q[j + 1]) { j++; } while (j <= tot && q[j] < q[i]) { swap(q[i], q[j]); i = j; j = i * 2; if(j + 1 <= tot && q[j] > q[j + 1]) j++;//不能忘 }}int main(){ cin>>n; for(int i = 1; i <= n; ++i){ int x;cin>>x; push(x); } for(int i = 1; i < n; ++i){ int x = top(); pop(); int y = top(); pop(); ans += x + y; push(x + y); } cout<<ans<<endl; return 0;}写的不是很好，也不全，但我会回来补充滴 o(︶︿︶)o