基礎數據結構淺談

• 棧是最基礎的數據結構，同時也是非常重要的一種數據結構。棧滿足後進先出原理，深入理解棧在面試當中很必要，因為棧不僅是面試當中的高頻考點，同時也是理解遞歸的必要條件。下面我首先為大家帶來兩道棧相關的題目

qscoj11

• 分析：本題需要求最長括弧匹配序列。我們可以用棧來進行維護，同時設置一個vis數組，每當有一對進行匹配時，把相應的兩個位置的下標置為1。最後統計最長連續1的長度就是所求。

#include<iostream>#include<cstdio>#include<cstring>#include<stack>using namespace std;const int maxn=100000+10;int vis[maxn];int main(){ int T; cin>>T; while(T--){ stack<int> que; string s; memset(vis,0,sizeof(vis)); cin>>s; int len=s.length(); for(int i=0;i<len;i++){ if(s[i]=="(") que.push(i); else{ if(!que.empty()){ vis[i]=1; vis[que.top()]=1; que.pop(); } } } int num=0,ans=0; for(int i=0;i<len;i++){ if(vis[i]) num++; else num=0; ans=max(ans,num); } cout<<ans<<endl; } return 0;}

poj2559

• 分析：樸素解法我們對於一個位置判斷題它向左最多能推多遠，向右最多能推多遠，時間複雜度O()，顯然是我們無法承受的。於是我們考慮用棧來進行維護。首先分析，對於某一個塊，若它的高度比它前面的一個塊小，則我們可以往左推，一直找到高度小於它的，這樣得到它最多往左推多少。同時我們將其入棧，然後再由後面的塊來對它進行同樣的操作，就能得到它最多能往右推多少，最後取其中的最大值就為所求。這樣的話，時間複雜度就大大降低。

#include<iostream>#include<cstdio>#include<cstring>#include<stack>using namespace std;const int maxn=100000+10;int h[maxn];int main(){ int n; while(cin>>n) { if(n==0) break; for(int i=1;i<=n;i++) scanf("%d",&h[i]); stack<int>que; que.push(0); h[++n]=0; long long ans=0; for(int i=1;i<=n;i++){ while(h[i]<h[que.top()]){ long long a=h[que.top()]; que.pop(); long long b=i-que.top()-1; ans=max(ans,a*b); } que.push(i); } cout<<ans<<endl; } return 0;}

poj3494

• 分析：這題就是上一題的二維版本，我們可以將其轉化為上一題的情形進行解答。我們可以以每一行作為基線，來統計其上由1組成的柱條的高度，若遇到0則h[j]置0，遇到1則h[j]+1，這樣，我們就轉化為求矩形的最大面積了，也就轉化成了上一題。

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<vector>#include<cctype>#include<algorithm>#include<set>#include<map>#include<stack>#include<queue>using namespace std;const int maxn=2000+10;int a[maxn][maxn];int h[maxn];int m,n;int main(){ while(cin>>m>>n) { for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); } } memset(h,0,sizeof(h)); int ans=0; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(a[i][j]==0) h[j]=0; else ++h[j]; } stack<int> s; s.push(0); h[++n]=0; for(int j=1;j<=n;j++){ while(h[j]<h[s.top()]){ int a=h[s.top()]; s.pop(); int b=j-s.top()-1; ans=max(ans,a*b); } s.push(j); } --n; } cout<<ans<<endl; } return 0;}

二。優先隊列

• 優先隊列也即是我們所說的堆，常與貪心演算法結合在一起來考察，注意大頂堆，小頂堆，以及結構體優先隊列的寫法

• 分析：把一堆數兩兩合併為2*sqrt(m1*m2)，求最終的最小值。類似哈夫曼樹，不過這次要先將大的合併，用一個優先隊列維護即可，優先隊列默認就是從大到小，即大頂堆

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <bitset>#include <cmath>#include <queue>#include <stack>using namespace std;int n;int main(){ while(cin>>n) { priority_queue<double>que; //優先隊列默認從大到小的順序 for(int i=0;i<n;i++) { double x; cin>>x; que.push(x); } double t1,t2,t; while(que.size()!=1) { t1=que.top(); que.pop(); t2=que.top(); que.pop(); t=2*sqrt(t1*t2); que.push(t); } printf("%.3lf
",que.top()); } return 0;}

poj3614

• 分析:有C個奶牛去曬太陽 (1 <=C <= 2500)，每個奶牛各自能夠忍受的陽光強度有一個最小值和一個最大值，太大就晒傷了，太小奶牛沒感覺。而剛開始的陽光的強度非常大，奶牛都承受不住，然後奶牛就得塗抹防晒霜，防晒霜的作用是讓陽光照在身上的陽光強度固定為某個值。那麼為了不讓奶牛燙傷，又不會沒有效果。給出了L種防晒霜。每種的數量和固定的陽光強度也給出來了.每個奶牛隻能抹一瓶防晒霜，最後問能夠享受曬太陽的奶牛有幾個。將奶牛按照可以忍受光強的最大值從小到大排序，然後用一個從小到大取數值的優先隊列維護各種防晒霜即可，即是小頂堆。

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <bitset>#include <cmath>#include <queue>#include <stack>using namespace std;const int maxn=2502;typedef struct p{ int minx,mx;}p;p s[maxn];int vis[maxn];int c,l;bool cmp(p a,p b){ return a.mx<b.mx;}int main(){ while(cin>>c>>l) { for(int i=0;i<c;i++) cin>>s[i].minx>>s[i].mx; memset(vis,0,sizeof(vis)); priority_queue<int,vector<int>, greater<int> > que; for(int i=0;i<l;i++){ int x,y; scanf("%d%d",&x,&y); for(int i=0;i<y;i++) que.push(x); } sort(s,s+c,cmp); int cnt=0; while(!que.empty()){ int t=que.top(); que.pop(); for(int i=0;i<c;i++){ if(!vis[i]&&t>=s[i].minx&&t<=s[i].mx){ vis[i]=1; cnt++; break; } } } cout<<cnt<<endl; } return 0;}

poj3262

• 分析:有n頭牛，每頭牛都有運輸出去所需時間以及每分鐘破壞的草的數量，每次運牛i出去需要時間2＊ti，這時其他牛在繼續破壞草，問怎麼才會使破壞的草的數量最小。我們可以這樣進行貪心：對任意一頭牛，例如：2 7，可以看成兩頭 1 3.5的牛，也就是說任意一頭牛都可以拆成T頭，1 D/T的牛。所以說，所有的牛就都變成了1 X。按照應該就X從大到小排序，最後用優先隊列搞定，注意結構體形式的優先隊列用法。

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <bitset>#include <cmath>#include <queue>#include <stack>using namespace std;const int maxn=100100;typedef struct p{ int t,d; double num; friend bool operator<(p a,p b) { return a.num<b.num; //大頂堆 }}p;int main(){ int n; while(cin>>n) { priority_queue<p> que; long long sum=0; for(int i=0;i<n;i++) { p s; scanf("%d%d",&s.t,&s.d); sum+=s.d; s.num=(double)s.d/(double)s.t; que.push(s); } long long cnt=0; while(!que.empty()) { p h=que.top(); que.pop(); sum-=h.d; cnt+=2*sum*h.t; } cout<<cnt<<endl; } return 0;}

三。樹狀數組

關於樹狀數組的基礎知識講解，推薦劉汝佳老師的《演算法競賽入門經典(訓練指南)》中的內容。

基礎知識

基礎題目

差分思想+樹狀數組

四。線段樹

關於線段樹的基礎講解，推薦楊弋的論文《線段樹》講稿

線段樹基礎題目

區間更新(Lazy操作)