数据结构(2012-noip)课件.pptVIP

数据结构专题;提纲;栈;栈的基本运算;栈的基本运算;音乐会的等待 问题描述：　　N个人排队，队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。 计算出有多少对人可以互相看见。 输入格式：　　第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。　　接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10-9米)为单位;音乐会的等待;音乐会的等待;音乐会的等待;音乐会的等待;音乐会的等待;音乐会的等待;音乐会的等待;音乐会的等待;音乐会的等待;音乐会的等待;const maxn=500000; var n,i,k,p,t :longint; push,num :array[0..maxn] of longint; ans :int64; begin readln(n); readln(k); p:=1; ans:=0; push[1]:=k; num[1]:=1; push[0]:=maxlongint; num[0]:=0; for i:=2 to n do begin readln(k); if kpush[p] then begin inc(ans); inc(p); push[p]:=k; num[p]:=1; end ;;;const maxn = 1000; var queue:array[1..maxn] of integer; front,back,counter:integer; procedure push(x:integer); begin inc(counter); inc(back); //这样的话front,back初始化为1,0 queue[back] :=x; end; function pop():integer; begin pop:=queue[front]; inc(front); dec(counter); end;;const int maxn=1000; int queue[maxn],counter=0, front=0,back= -1 ; void push(int x){ queue[++back]=x;++counter; } int pop(){ --counter; return queue[front++]; };队列;队列操作;队列的应用;PKU 2823 Sliding Window;PKU 2823 Sliding Window;PKU 2823 Sliding Window;PKU 2823 Sliding Window;PKU 2823 Sliding Window;单调队列;单调队列;假设数列为：8，7，12，5，16，9，17，2，4，6.N=10,k=3. 那么我们构造一个长度为3的单调递减队列： 首先，把8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下： 0：插入8，队列为：（8，0） 1：插入7，队列为：（8，0），（7，1） 2：插入12，队列为：（12，2） 3：插入5，队列为：（12，2），（5，3） 4：插入16，队列为：（16，4） 5：插入9，队列为：（16，4），（9，5） …… 那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，……;PKU 2823 Sliding Window;bool empty(){??? if(h=t)return 0;??? else return 1;}void max_min(int flag){???? h=1;t=0;???? for(int i=1;i=n;i++)???? {???????????? while(!empty()(i+1-index[h]k))++h;// 保持k个???????????? if(flag)???????????? while(!empty()(a[i]=b[t]))t--;???????????? else???????????? while(!empty()(a[i]=b[t]))t--;// 删除不满足条件的队尾数值???????????? b[++t]=a[i];???????????? index[t]=i;???? ??????? if(i=k)??????? {???????????? if(ik)printf( );???????