貪心

定義

貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇，也就是說，不從整體最優上加以考慮，只做出在某種意義上的區域最優解，貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的程序不會影響以后的狀態，只與當前狀態有關，

平時購物找零錢時，為使找回的零錢的硬幣數最少，不要求找零錢的所有方案，而是從最大面值的幣種開始，按遞減的順序考慮各面額，先盡量用大面值的面額，當不足大面值時才去考慮下一個較小面值，這就是貪心演算法

使用條件

• 貪心選擇性質
  一個問題的整體最優解可通過一系列區域的最優解的選擇達到，并且每次的選擇可以依賴以前作出的選擇，但 不依賴于后面要作出的選擇 ，這就是貪心選擇性質，
• 最優子結構性質
  當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質，問題的最優子結構性質是該問題可用貪心法求解的關鍵所在，在實際應用中，至于什么問題具有什么樣的貪心選擇性質是不確定的，需要具體問題具體分析，

解題程序

解題的一般步驟是：

1. 建立數學模型來描述問題；
2. 把求解的問題分成若干個子問題；
3. 對每一子問題求解，得到子問題的區域最優解；
4. 把子問題的區域最優解合成原來問題的一個解，

缺點

1. 不能保證解是最佳的，因為貪心演算法總是從區域出發，并沒從整體考慮；
2. 貪心演算法一般用來解決求最大或最小解，

例題

• 新生賽：Time management（小植哥哥南京站打比賽做多能做幾個題）

  已知主辦方一共出了N道題，多人運動隊計劃每道題在 S i S_i Si?時刻開始做，在 E i E_i Ei?時刻做完，一次只能同時做一道題，比賽結束后，他們最多能過多少題呢？

• 原題：[USACO09DEC]Selfish Grazing S

  Each of Farmer John’s N ( 1 ≤ N ≤ 50 , 000 ) N (1 \leq N \leq 50,000) N(1≤N≤50,000) cows likes to graze in a certain part of the pasture, which can be thought of as a large one-dimeensional number line. Cow i’s favorite grazing range starts at location S_i and ends at location E i ( 1 ≤ S i < E i ; S i < E i ≤ 100 , 000 , 000 ) E_i (1 \leq S_i < E_i; S_i < E_i \leq 100,000,000) Ei?(1≤Si?<Ei?;Si?<Ei?≤100,000,000).
  Most folks know the cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows i and j can only graze at the same time if either S i ≥ E j S_i \geq E_j Si?≥Ej? or E i ≤ S j E_i \leq S_j Ei?≤Sj?. FJ would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences.
  Consider a set of 5 cows with ranges shown below:
  
  These ranges represent (2, 4), (1, 12), (4, 5), (7, 10), and (7, 8), respectively.
  For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.
  約翰有 N ( 1 ≤ N ≤ 50000 ) N(1≤N≤50000) N(1≤N≤50000)頭牛，約翰的草地可以認為是一條直線．每只牛只喜歡在某個特定的范圍內吃草．第i頭牛喜歡在區間 ( S i ， E i ) (S_i，E_i) (Si?，Ei?)吃草， 1 ≤ S i < E i ≤ 1 , 000 , 000 , 00 1≤S_i<E_i≤1,000,000,00 1≤Si?<Ei?≤1,000,000,00.
  奶牛們都很自私，他們不喜歡和其他奶牛共享自己喜歡吃草的領域，因此約翰要保證任意
  兩頭牛都不會共享他們喜歡吃草昀領域．如果奶牛i和奶牛J想要同時吃草，那么要滿足： S i ≥ E j S_i\geq E_j Si?≥Ej?或者 E i ≤ S j E_i\leq S_j Ei?≤Sj?．約翰想知道在同一時刻，最多可以有多少頭奶牛同時吃草？

這道題在《演算法導論》里叫做活動選擇問題，

• 活動選擇問題
  問題是調度競爭共享資源的多個活動，目標是選出一個最大的互相兼容的活動集合，
  假定有 n n n個活動的集合 S = { a 1 , a 2 , . . . , a n } S=\{a_1,a_2,...,a_n\} S={a1?,a2?,...,an?}，這些活動使用同一資源，并且在同一時刻只能供一個活動使用，每個活動 a i a_i ai?都會有一個開始時間 s i s_i si? 和一個結束時間 f i f_i fi? ，其中 0 ≤ s i ≤ < f i < ∞ 0\leq s_i\leq<f_i<\infty 0≤si?≤<fi?<∞，選中某活動，該活動發生在 [ s i , f i ) [s_i,f_i) [si?,fi?)若有兩個活動無重疊時間段，則稱他們為兼容的，我們希望選出一個最大兼容活動集

這個問題還可以再變：

一個數軸上有n條線段，選取其中a條線段使得這a條線段都不重合，求最大的a

解題思路：按照右端點排個序（只有右端點才會對后續時間有影響），然后依次貪心往進放就可，

#include<iostream>
#include<algorithm>
using namespace std;
struct moo
{
	int x,y;
}cow[500005];
bool comp(moo a,moo b)
{
	return a.y<b.y;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>cow[i].x>>cow[i].y;
	sort(cow+1,cow+n+1,comp);
	int r=0,ans=0;
	for(int i=1;i<=n;i++)
		if(cow[i].x>=r)
		{
			ans++;
			r=cow[i].y;
		}
	cout<<ans;
	return 0;
}

動態規劃

基本思想

全域最優解如果可以由子問題的最優解推導得到，則可以先求解子問題的最優解，再構造原問題的最優解；若子問題有較多的重復出現，則可以自底向上從最終子問題向原問題逐步求解，

分類

從一道題認識動態規劃：數字三角形

給出一個數字三角形，從頂部到底部有很多路徑，求路徑最大和，
輸入：
第一行一個n，表示共有幾行
后面n行，數字三角形，
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出：一個整數答案
32

dfs

從起點開始，向下進行遞回求當前點最大值，每一步只能走(x+1,y+1)或(x+1,y)，終止條件為遞回到第n行，

#include<stdio.h>
int n;
int a[10][10];
int MAX(int x,int y)
{
	return x>y?x:y;
}
int dfs(int x,int y)//<algorithm>
{
	if(x==n)return a[x][y];
	return a[x][y]+MAX(dfs(x+1,y+1),dfs(x+1,y));
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	printf("%d",dfs(1,1));
	return 0;
}

記憶化dfs

在樸素的遞回中有大量重復的運算，把重復運算的結果記錄下來，能夠有效提高效率

#include<stdio.h>
int n;
int a[10][10];
int b[10][10];//存中間重復計算值 
int MAX(int x,int y)
{
	return x>y?x:y;
}
int dfs(int x,int y)//max -> <algorithm>
{
	if(x==n)return a[x][y];
	if(b[x][y])return b[x][y];
	return b[x][y]=a[x][y]+MAX(dfs(x+1,y+1),dfs(x+1,y));
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	printf("%d",dfs(1,1));
	return 0;
}

dp

實際上每一次遞回都是改變現有題目規格，使規模不斷變小，分而治之，分析遞回實際的程序會發現本質上其實程式在執行一個從下到上遞推的程序，利用陣列來描述這個遞推的程序，也就是所謂動態規劃，中間用來計算遞推狀態的公式就叫做狀態轉移方程，

#include<stdio.h>
int n;
int a[10][10];
int f[10][10];
int MAX(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	
	for(int i=n;i;i--)
		for(int j=1;j<=i;j++)
			f[i][j]=MAX(f[i+1][j+1],f[i+1][j])+a[i][j];
	printf("%d",f[1][1]);
	return 0;
}

做題思路

1. 分解成若干子問題；
2. 確定狀態轉移方程，考慮怎么樣從上一個狀態變換成下一個狀態
3. 確定邊界條件

題目特點

• 問題具有最優子結構性質，如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質，
• 無后效性
  每個狀態都是過去歷史的一個完整總結，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態，

背包問題

一種組合優化的NP完全問題（多項式復雜程度的非確定性問題），

P：多項式時間內能解決的判定問題，
NP：所有的非確定性多項式時間可解的判定問題
NPC：NP完全問題，這些問題中任何一個如果存在多項式時間的演算法,那么所有NP問題都是多項式時間可解的.這些問題被稱為NP-完全問題(TSP)

給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高，
也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？
它是在1978年由Merkle和Hellman提出的，
背包問題深入研究強烈安利《背包九講》（馬：6666），
b站acwing yxc講背包九講

01背包

• 題面

  有 N N N 件物品和一個容量為 V V V 的背包，放入第 i i i 件物品耗費的費用是 C i C_i Ci?，得到的價值是 W i W_i Wi?，求解將哪些物品裝入背包可使價值總和最大，

• 特點
  每個物品只有一件，放或者不放
• 狀態轉移方程： f [ i , v ] f[i,v] f[i,v]表示 i i i 個物品， v v v 個容量 的最大價值是 f f f，
  f [ i , v ] = m a x { f [ i ? 1 , v ] , f [ i ? 1 , v ? C i ] + W i } f[i,v] = max\{~f[i-1, v]~,~ f[i-1, v-C_i] + W_i~\} f[i,v]=max{ f[i?1,v] , f[i?1,v?Ci?]+Wi? }

基本上所有跟背包相關的問題的方程都是由它衍生出來的，

• 若只考慮第 i i i 件物品的策略（放或不放），那么就可以轉化為一個只和前 i ? 1 i-1 i?1 件物品相關的問題，
• 如果不放第 i i i 件物品，那么問題就轉化為“前 i ? 1 i-1 i?1 件物品放入容量為 v v v 的背包中”，價值為 F [ i ? 1 , v ] F[i-1, v] F[i?1,v]
• 如果放第 i i i 件物品，那么問題就轉化為“前 i ? 1 i-1 i?1 件物品放入容量為 v ? C i v-C_i v?Ci? 的背包中”，此時能獲得的最大價值就是 F [ i ? 1 , v ? C i ] F[i-1, v-C_i] F[i?1,v?Ci?] 再加上通過放入第 i i i 件物品獲得的價值 W i W_i Wi?，
• 優化：時空復雜度為 O ( V N ) O(VN) O(VN)，稍加優化可以將空間復雜度降到 O ( V ) O(V) O(V)

補充：關于時間復雜

常見的的復雜度比較： O ( 1 ) < O ( log ? n ) < O ( n ) < O ( n l o g n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( 3 n ) < O ( n ! ) O(1) < O(\log n) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(3^n) < O(n!) O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(3n)<O(n!)

例題：[NOIP2005 普及組] 采藥

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師，為此，他想拜附近最有威望的醫師為師，醫師為了判斷他的資質，給他出了一個難題，醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值，我會給你一段時間，在這段時間里，你可以采到一些草藥，如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大，”

代碼：純裸的01背包問題

#include<iostream>
using namespace std;
int A[120][22000],T[120],V[120];
int main()
{
	int t,m;
	cin>>t>>m;
	for(int i=1;i<=m;i++)
		scanf("%d%d",&T[i],&V[i]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++)
			if(j>=T[i])
				A[i][j]=max(A[i-1][j],A[i-1][j-T[i]]+V[i]);
			else
				A[i][j]=A[i-1][j];
	cout<<A[m][t];
	return 0;
}

從C到C++

對于像ACM這種對時間要求高的編程競賽，相對于其他語言來說，更適合用c++去寫程式，c++相比較來說有著豐富的函式庫，封裝了大量現成的模板，演算法，有可以拿來直接用的STL，并且不論是實作時間還是運行時間都要比現場手寫的效果好，

輸入輸出

與c的scanf和printf不同，c++使用iosteam來進行輸入輸出，

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	cout<<n<<endl;
	return 0;
}

c++使用一個全面的標準庫來提供IO機制，cin,cout操作就包含在iostream頭檔案里，在預處理部分首先參考iostream庫，該庫包含了兩個基礎型別istream和ostream，分別表示輸入流和輸出流，“流”表示從IO設備讀出或寫入的字符序列，
標準庫定義了4種IO物件，另外的兩個為cerr和clog，通常用cerr輸出警告和錯誤資訊，用clog輸出程式運行時資訊，混合使用cout,cerr,clog時，程式會將他們寫在同一個視窗里，
注意，c++頭檔案不帶.h后綴，在c++里使用c的頭檔案時，前面加c后面去掉.h，具體如下：

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>

endl是個操縱符(manipulator)，效果就像\n結束當前行，并將與設備關聯的緩沖區(buffer)重繪到設備中，重繪緩沖可以保證當前所有的輸出真正寫到輸出流中，而不是在設備中等待寫入流，
>>，<<分別為輸入和輸出運算子，可以利用輸入輸出運算子進行連續輸出和輸入，比如這樣：

#include<iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	cout<<n+m<<' '<<n-m<<endl;
	return 0;
}

可以進行根據變數型別自動匹配，比如這樣：

#include<iostream> 
using namespace std;
int main()
{
	int n;
	double m;
	cin>>n>>m;
	cout<<n<<' '<<m<<endl;
	return 0;
}

可以加常量字串，比如這樣：

#include<iostream> 
using namespace std;
int main()
{
	int n;
	double m;
	cin>>n>>m;
	cout<<"剛剛輸入的整數是"<<n<<"，剛剛輸入的浮點數是"<<m<<endl;
	return 0;
}

是不是肥腸滴銀杏，
同時cin,cout是被定義在std命名空間里的，如果不加using會是這個樣子

#include<iostream>
int main()
{
	int n;
	std::cin>>n;
	std::cout<<n<<std::endl;
	return 0;
}

其中::為作用域運算子，編譯器從他左側的作用域中找右邊的名字，如果使用using宣告可以在參考名空間成員時不必使用名空間限定符::，
但是其實精通C++后都不建議寫using namespace std;這句話，完整一點說應該是“盡量不擴大using namespace xxx所影響到的域”，也就是說不要在頭檔案里用這句話，《c++ primer》里作者在第三章3.1命名空間的using宣告p75頁提到：

頭檔案的內容會拷貝到所有參考他的檔案中去……對于某些程式來說，由于不經意間包含了一些名字，反而可能產生始料未及的名字沖突，

《C++ Primer Plus》在第九章:記憶體模型和名稱空間 第329頁提到

一般說來，使用using命令比使用using編譯命令更安全，這是由于它只匯入了制定的名稱，如果該名稱與區域名稱發生沖突，編譯器將發出指示，using編譯命令匯入所有的名稱，包括可能并不需要的名稱，如果與區域名稱發生沖突，則區域名稱將覆寫名稱空間版本，而編譯器并不會發出警告，另外，名稱空間的開放性意味著名稱空間的名稱可能分散在多個地方，這使得難以準確知道添加了哪些名稱，

目前如果只是些演算法競賽的話就什么都不管把這句話每次都寫上就可以，不會出現什么問題，

輸入輸出速度分析

眾所周知cin比scanf慢的不是一點，原因是cin與stdin總是保持同步的，也就是說這兩種方法可以混用，同時cout和stdout也一樣，兩者混用不會輸出順序錯亂，正因為這個兼容性的特性，導致cin有許多額外的開銷，實際上可以用sync_with_stdio(false);關閉同步流（但有的時候還是會玄學速度），
但是還有選手對這樣的速度還是不滿意，所以他們直接用快讀來輸入輸出，原理就是先一直讀入字符直到出現數字，再一直讀入數字同時累乘直到讀入的不是數字，優化核心在于getchar的速度很快，

inline int redn() {
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

輸出優化同理，但是單純的輸出優化還沒printf快，就不用騷操作了，
還有選手用fread優化，fread直接快到飛起啊，原理就是讓fread一次性讀入大量資料，再讓getchar直接呼叫記憶體，如果剛開始讀的不夠多那就再呼叫fread讀入資料，直到檔案的末尾，
附一個luogu神仙用iostream底層的streambuf操作的基于streambuf的IO優化
實際上，正常的比賽好好的靈活運用cin,cout,scanf,printf就夠了，，，

行內函式

行內函式(inline)可以避免函式呼叫的開銷，并且只是向編譯器發出一個請求，編譯器可以自己選擇是否忽略掉這個請求，
一般行內用于優化規模小的，流程直接，頻繁呼叫的函式，并且很多編譯器都不支持行內用于遞回，

STL標準模板庫

標準模板庫（Standard Template Library）是惠普實驗室開發的一系列軟體的統稱，被容納于C++標準程式庫（C++ Standard Library）中是標準庫的核心，是一個泛型(generic)程式庫，STL的代碼從廣義上講分為三類：algorithm（演算法）、container（容器）和iterator（迭代器），幾乎所有的代碼都采用了模板類和模板函式的方式，

概述

在C++標準中，STL被組織為下面的13個頭檔案：

#include<algorithm>
#include<deque>
#include<functional>
#include<iterator>
#include<vector>
#include<list>
#include<map>
#include<memory>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>

[這段看不懂就算了，想看懂了到時候深入研究一下c++吧]STL的一個重要特點是資料結構和演算法的分離，這種分離確實使得STL變得非常通用，例如，由于STL的sort()函式是完全通用的，你可以用它來操作幾乎任何資料集合，包括鏈表，容器和陣列；另一個重要特性是它不是面向物件的，為了具有足夠通用性，STL主要依賴于模板，在STL中找不到任何明顯的類繼承關系，這使得STL的組件具有廣泛通用性的底層特征，另外，由于STL是基于模板，行內函式的使用使得生成的代碼短小高效，從邏輯層次來看，在STL中體現了泛型化程式設計的思想，引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），演算法（algorithmn），迭代子（iterator）等，與OOP（object-oriented programming）中的多型（polymorphism）一樣，泛型也是一種軟體的復用技術；從實作層次看，整個STL是以一種型別引數化的方式實作的，

容器

容器用來管理某類物件，簡單的理解容器，它就是一些模板類的集合，但和普通模板類不同的是，容器中封裝的是組織資料的方法（也就是資料結構），說白了容器就是存放資料的東西，再傻瓜點的理解就是容器就像陣列一樣，
STL提供了關聯式，順序式和特殊容器，容器配接器，容器配接器是容器配接，也就是利用請其實作出來的結構叫容器配接器，

字串

string是可變長字符序列（就是字串…），定義如下：

namespace std
{
	template<class T,//字符所屬型別,ASCII,Unicode...
		class traits=char_traits<charT>,//traits class，提供字串核心操作，
		 class Allocator=allocator<charT> >//記憶體模型
	class basic_string;
	typedef basic_string<char> string;
	typedef basic_string<wchar_t> wstring;//寬字符，像Unicode
}

string支持用下標訪問，
string可以用length()或者size()來回傳string::size_type型別的大小，
關于string的更多見我的另一篇關于string的總結

• 例題

動態陣列

vector是一個能夠存放任意型別的動態陣列，在<vector>定義如下：

namespace std
{
	template <class T,//元素型別
			  class Allocator=allocator<T> >//記憶體的模型，默認使用allocator
	class vector;
}

初始化方法：

vector<T> v1;//定義了一個能裝T型別(ElementType)的空v1
vector<T> v2(v1)；//v2是v1副本
vector<T> v2=v1;//同上
vector<T> v3(n,val);//v3里有n個val
vector<T> v4(n);//v4有n個空位置
vector<T> v5{a,b,c};//賦初值a,b,c
vector<T> v5={a,b,c};//同上

vector支持隨機存取，并且支持類似陣列操作，所以可以在常數時間記憶體取任意元素，：

array[i]=num;
array.at(i)=num;

以上兩句話等效，并且后者還會在陣列越界時拋出例外，但是只能對已知確定存在的元素進行訪問操作！不能對空容器操作，不能用下標形式添加元素！通過下標訪問不存在元素會產生緩沖區溢位(buffer overflow)，
vector在末端操作時非常快，但是在中間或者前面就慢了，是因為前面或中間操作的話，后面的元素都要隨著動，每次一動都要調assignment(賦值)運算子，
vector可以通過size()回傳目前有多少元素，可以用capacity()回傳當前容器容量，當容器容量等于元素數量，也就是size()==capacity()，即容器已滿時，vector會進行擴容，擴容并非簡單的在容器尾部申請空間然后存盤新的元素，而是會申請一個新的空間，然后把原有的元素拷貝過去，再釋放掉原有的空間，容器整體搬家了！ 所以在擴容后之前的所有迭代器都失效了，
一般vector擴容會申請比原來容量多一倍的空間，devcpp就是如此，但vs2019增加了4，2倍擴容時間復雜度更優，可以保證時間復雜度 O ( n ) O(n) O(n) ，而1.5倍擴容時，空間可重用，各有利弊，

• 例題

堆疊

先手寫一個堆疊實作三個功能：入堆疊，查詢堆疊頂，出堆疊，

#include<iostream>
#define STACK_SIZE 5
using namespace std;
int s[STACK_SIZE];
int top;
inline void s_push(int val)
{
	if(top<STACK_SIZE-1)s[++top]=val;
	else cerr<<"stack over flow"<<endl;
}
inline int s_top()
{
	return s[top];
}
inline void s_pop()
{
	if(top)top--;
	else cerr<<"stack under flow"<<endl;
}
inline int s_size()
{
	return top;
}
inline bool s_empty()
{
	return top==0;
}
int main()
{
	int n;//n個操作 
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int op,num;
		cin>>op;
		if(op==1)//入堆疊
		{
			cin>>num;
			s_push(num);
		}
		if(op==2)cout<<"top: "<<s_top()<<endl;//查詢堆疊頂 
		if(op==3)s_pop();//出堆疊
		if(op==4)cout<<"size: "<<s_size()<<endl;
		if(op==5)cout<<"empty:"<<(s_empty()?"true":"false")<<endl;
	} 
	return 0;
}	

STL提供了堆疊的容器配接器，核心介面是三個成員函式push(),top(),pop()，還有size()和empty()兩個常用介面;

在頭檔案<stack>中，class stack定義如下：

namespace std
{
	template <class T,//元素型別
			  class Container=deque<T> >//所使用的容器，預設采用deque，不選用vector是因為deque移除元素后會釋放記憶體
	class stack;
}

宣告這么寫：

std::stack<int>st;//用了using就不用寫std作用域

如果要換個序列式容器來實作stack，就可以這么整，比如說vector：

stack<int,vector<int> >st;

把剛剛手寫的堆疊用STL重新實作：

#include<iostream>
#include<stack>
using namespace std;
stack<int>s;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,num;
		cin>>op;
		if(op==1)
		{
			cin>>num;
			s.push(num);
		}
		if(op==2)cout<<"top: "<<s.top()<<endl;
		if(op==3)s.pop();
		if(op==4)cout<<"size: "<<s.size()<<endl;
		if(op==5)cout<<"empty:"<<(s.empty()?"true":"false")<<endl;
	}
	return 0;
}

佇列

先手寫一個佇列

#include<iostream>
#define QUEUE_SIZE 100005
using namespace std;
int q[QUEUE_SIZE];
int front,back;
inline void q_push(int val)
{
	if((front+1)%QUEUE_SIZE!=back)
	{
		front=(front+1)%QUEUE_SIZE;
		q[front]=val;
	}
	else cerr<<"queue over flow"<<endl;
}
inline bool q_empty()
{
	return back==front?true:false;
}
inline void q_pop()
{
	if(!q_empty())back=(back+1)%QUEUE_SIZE;
	else cerr<<"queue under flow"<<endl;
}
inline int q_front()
{
	return q[front];
}
inline int q_back()
{
	return q[(back+1)%QUEUE_SIZE];
}
inline int q_size()
{
	return (front-back+QUEUE_SIZE)%QUEUE_SIZE;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,num;
		cin>>op;
		if(op==1)
		{
			cin>>num;
			q_push(num);
		}
		if(op==2)cout<<"back: "<<q_back()<<endl;
		if(op==3)cout<<"front: "<<q_front()<<endl;
		if(op==4)q_pop();
		if(op==5)cout<<"size: "<<q_size()<<endl;
		if(op==6)cout<<"empty: "<<(q_empty()?"true":"false")<<endl;
	}
	return 0;
}

STL提供了佇列的容器配接器，與這里手寫的不同的是，STL將后入佇列元素放到了back，先出從front，

在頭檔案<queue>中，class queue定義如下：

namespace std
{
	template <class T,//元素型別
		  class Container=deque<T> >//所使用的容器，預設采用deque
	class queue;
}

宣告這么寫：

queue<string>q;

同樣如果要換個序列式容器來實作queue，就可以這么整，比如說list：

stack<int,list<int> >st;

把剛剛手寫的佇列用STL重新實作：

#include<iostream>
#include<queue>
using namespace std;
queue<int>q;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,num;
		cin>>op;
		if(op==1)
		{
			cin>>num;
			q.push(num);
		}
		if(op==2)cout<<"back: "<<q.back()<<endl;
		if(op==3)cout<<"front: "<<q.front()<<endl;
		if(op==4)q.pop();
		if(op==5)cout<<"size: "<<q.size()<<endl;
		if(op==6)cout<<"empty: "<<(q.empty()?"true":"false")<<endl;
	}
	return 0;
}

優先佇列

普通的佇列是一種先進先出的資料結構，元素在佇列尾追加，而從佇列頭洗掉，在優先佇列中，元素被賦予優先級，當訪問元素時，具有最高優先級的元素最先洗掉，優先佇列具有最高級先出 （first in, largest out）的行為特征，通常采用堆資料結構來實作，
堆是一顆完全二叉樹，堆中的某個父結點的值總是大于等于（最大堆）或小于等于（最小堆）其孩子結點的值，每個結點的子樹都是堆樹，一般操作進行一次的時間復雜度在O(1)~O(logn)之間，常見的堆有二叉堆、斐波那契堆等，
堆中核心操作在于上浮和下沉：

• 在堆中插入新元素時，將新元素放在尾部，然后向上逐步上浮；
• 在堆中彈出優先級最高的根結點元素時，讓根節點元素和尾節點進行交換，然后讓現在的根元素下沉就可以了，

安利博客：基本資料結構――堆的基本概念及其操作
啊哈演算法中有堆的模擬的代碼

#include <stdio.h>
int h[ 101];//用來存放堆的陣列
int n;//用來存盤堆中元素的個數，也就是堆的大小


//交換函式，用來交換堆中的兩個元素的值
void swap(int x,int y)
{
    int t;
    t=h[ x];
    h[ x]=h[ y];
    h[ y]=t;
}


//向下調整函式
void siftdown(int i) //傳入一個需要向下調整的結點編號i，這里傳入1，即從堆的頂點開始向下調整
{
    int t,flag=0;//flag用來標記是否需要繼續向下調整
    //當i結點有兒子的時候（其實是至少有左兒子的情況下）并且有需要繼續調整的時候回圈窒執行
    while( i*2<=n && flag==0 )
    {        
        //首先判斷他和他左兒子的關系，并用t記錄值較小的結點編號
        if( h[ i] > h[ i*2] )
            t=i*2;
        else
            t=i;
        //如果他有右兒子的情況下，再對右兒子進行討論
        if(i*2+1 <= n)
        {
            //如果右兒子的值更小，更新較小的結點編號  
            if(h[ t] > h[ i*2+1])
                t=i*2+1;
        }
        //如果發現最小的結點編號不是自己，說明子結點中有比父結點更小的  
        if(t!=i)
        {
            swap(t,i);//交換它們，注意swap函式需要自己來寫
            i=t;//更新i為剛才與它交換的兒子結點的編號，便于接下來繼續向下調整
        }
        else
            flag=1;//則否說明當前的父結點已經比兩個子結點都要小了，不需要在進行調整了
    }
}


//建立堆的函式
void creat()
{
    int i;
    //從最后一個非葉結點到第1個結點依次進行向上調整
    for(i=n/2;i>=1;i--)
    {
        siftdown(i);
    }  
}


//洗掉最大的元素
int deletemax()
{
    int t;
    t=h[ 1];//用一個臨時變數記錄堆頂點的值
    h[ 1]=h[ n];//將堆得最后一個點賦值到堆頂
    n--;//堆的元素減少1
    siftdown(1);//向下調整
    return t;//回傳之前記錄的堆得頂點的最大值
}


int main()
{
    int i,num;
    //讀入數的個數
    scanf("%d",&num);


    for(i=1;i<=num;i++)
        scanf("%d",&h[ i]);
    n=num;   

    //建堆
    creat();

    //洗掉頂部元素，連續洗掉n次，其實夜就是從大到小把數輸出來
    for(i=1;i<=num;i++)
        printf("%d ",deletemax());

    getchar();
    getchar();
    return 0;
}

• 例：TJOI2010 中位數

  給定一個由N個元素組成的整數序列，現在有兩種操作：
  1 add a
  在該序列的最后添加一個整數a，組成長度為N + 1的整數序列
  2 mid 輸出當前序列的中位數
  例1：1 2 13 14 15 16 中位數為13
  例2：1 3 5 7 10 11 17 中位數為7
  例3：1 1 1 2 3 中位數為1

  有人用主席樹，堆，線段樹，splay，fhq treap，tarjan 的Zip tree，還有暴力，這道題也可以用兩個堆來維護中位數，
  將所有數先放到大根堆里去，然后取一半再放到小根堆，這樣就是有序的兩部分，add時取小根堆頂和add數比較大于堆頂加入小根堆，否則加入大根堆（維護有序）
  mid時為了保證大根堆頂就是答案，就應該控制讓大根堆里的元素為(all+1)>>1，從小根堆那里多退少補，最后直接輸出大根堆頂就行，
  代碼如下：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_q<int,vector<int>,greater<int> >q1;//xiao
priority_q<int,vector<int>,less<int> >q2;//da
string s;
int cnt1,cnt2;
int main()
{
	int n,m;
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		int a;
		cin>>a;
		q2.push(a);
		cnt2++;
	}
	for(int i=1; i<=n/2; i++)
	{
		int x=q2.top();
		q2.pop();
		cnt2--;
		q1.push(x);
		cnt1++;
	}
	cin>>m;
	for(int i=1; i<=m; i++)
	{
		cin>>s;
		if(s[0]=='a')
		{
			int x;
			cin>>x;
			n++;
			int l=q2.top();
			if(x>l)q1.push(x),cnt1++;
			else q2.push(x),cnt2++;
		}
		else
		{
			while(cnt2<((n+1)>>1))
			{
				int x=q1.top();
				q1.pop();
				cnt1--;
				q2.push(x);
				cnt2++;
			}
			while(cnt2>((n+1)>>1))
			{
				int x=q2.top();
				q2.pop();
				cnt2--;
				q1.push(x);
				cnt1++;
			}
			if(cnt2==((n+1)>>1))
				cout<<q2.top()<<endl;
		}
	}
	return 0;
}

迭代器

類似于指標，迭代器也提供了物件的間接訪問，使用迭代器可以訪問某元素，也能從一個元素移動到另一個元素，和指標一樣，迭代器也分為有效和無效之分，
和指標的區別在于，獲取迭代器不是使用的取地址，有迭代器的型別同時擁有回傳迭代器的成員，

演算法

標準庫定義了一組泛型演算法，稱之為“泛型”是因為：實作了經典演算法的公共介面，不游標準庫型別，甚至陣列之類的都可以用，
大多演算法定義在<algorithm>里，其中也包含了許多輔助函式：max(),min(),swap()等等，是不是肥腸滴銀杏，

排序

對于排序來說，時間效率是最重要的，所以STL提供了多個排序演算法，最常用的就是sort()
sort內部采用快排的思想，保證了平均性能，復雜度為 O ( n l o g n ) O(nlogn) O(nlogn)，但最差情況也有可能降到 O ( n 2 ) O(n^2) O(n2)，準確來書它實際采用Introspective Sorting(內省式排序)，資料量大時用快排，一旦分段后的資料量小于某個門坎，為避免快排的遞回呼叫帶來過大的額外負荷，就改用插排，如果遞回層次過深，還會改用堆排，所以手寫快排時，哪怕是尾遞回式的快排也不會有它快，（意思就是絕對比你自己手寫的快排要快，如果你寫的比sort還要快，那你就可以當新的STL了(doge)），
sort的寫法有兩種形式：

//sort(beg,end):
int a[100]={0,5,4,2,3,8,6,9,7,8,6};
sort(a+1,a+10+1);
/
//sort(beg,end,comp:
bool comp(int a,int b)
{
	return a>b;//從大到小順序排列
}
int main()
{
int a[100]={0,5,4,2,3,8,6,9,7,8,6};
sort(a+1,a+10+1,comp;
}