STL容器
vector
堆疊
佇列
鏈表
set
map
sort函式
next_permulation函式
容器
1.順序式容器:vector,list,deque,queue,priority_queue,stack等;
2.關聯式容器:set,multiset,map,multimap等
vector

vector容器能存放任何型別的物件:


| 功能 | 例子 | 說明 |
|---|---|---|
| 賦值 | a.push_back(100); | 在尾部添加元素 |
| 元素個數 | int size=a.size(); | 元素個數 |
| 是否為空 | bool is Empty=a.empty(); | 判斷是否為空 |
| 列印 | cout<<a[0]<<endl; | 列印第一個元素 |
| 中間插入 | a.insert(a.begin()+i,k); | 在第i個元素前面插入k |
| 洗掉尾部 | a.pop_back(); | 洗掉末尾元素 |
| 洗掉區間 | a.erase(a.begin()+i,a.begin()+j); | 洗掉區間[i,j-1]的元素 |
| 洗掉元素 | a.erase(a.begin()+2) | 洗掉第三個元素 |
| 調整大小 | a.resize(n,num) | 陣列大小變為n,若長于原大小,則剩下位置由num補 |
| 清空 | a.clear(); | |
| 翻轉 | a.reverse(a.begin(),a.end()); | 用函式reverse翻轉陣列 |
| 排序 | sort(a.begin(),a.end()); | 用函式sort排序,從小到大 |

圓桌上圍坐著2n個人,其中n個人是好人,另外n個人是壞人,如果從第一個人開始數數,數到第m個人,則立即處死該人;然后從被處死的人之后開始數數,再將數到的第m個人處死……依此方法不斷處死圍坐在圓桌上的人,試問預先應如何安排這些好人與壞人的座位,能使得在處死n個人之后,圓桌上圍坐的剩余的n個人全是好人,
Input
多組資料,每組資料輸入:好人和壞人的人數n(<=32767)、步長m(<=32767);
Output
對于每一組資料,輸出2n個大寫字母,‘G’表示好人,‘B’表示壞人,50個字母為一行,不允許出現空白字符,相鄰資料間留有一空行,
Sample Input
2 3
2 4
Sample Output
GBBG
代碼如下:
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
int flag[50017];
vector<int>v;
int main()
{
int n,m;
int tot,now;
int i;
while(~scanf("%d%d",&n,&m))
{
v.clear();
tot=2*n;
for(i=1;i<=tot;i++)
{
v.push_back[i];
flag[i]=0;
}
now=1;
while(tot>n)//僅僅尋找壞人
{
now+=(m-1);
if(now<=tot)
{
flag[v[now-1]]=1;
v.erase(v.begin()+now-1);
now=(now==tot?1:now);
}
else
{
now%=tot;
now=(now==0?tot:now);
flag[v[now-1]]=1;
v.erase(v.begin()+now-1);
now=(now==tot?1:now);
}
tot--;
}
for(i=1;i<=2*n;i++)
{
if(flag[i])
prinytf("B");
else
printf("G");
if(i%50==0)
printf("\n");
}
if(2*n%50!=0)
printf("\n");
}
}
這類問題實際上是約瑟夫問題,常用vector模擬動態變化的圓桌,代碼可精簡為:
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<int>table;//模擬圓桌
int n,m;
while(cin>>n>>m)
{
table.clear();
for(int i=0;i<2*n;i++)
table.push_back(i);//初始化
int pos=0;//記錄當前位置
for(int i=0;i<n;i++)//趕走n個
{
pos=(pos+m-1)%table.size();
//圓桌是個環,取余處理
table.erase(table.begin()+pos);
//趕走壞人,table人數減1
}
int j=0;
for(int i=0;i<2*n;i++)
{//列印預定安排座位
if(!(i%50)&&i)cout<<endl;
//50個字母一行
if(j<table.size()&&i==table[j])
{//table留下的都是好人
j++;
cout<<"G";
}
else
cout<<"B";
}
cout<<endl;
}
return 0;
}
堆疊和stack
堆疊:基本的資料結構之一,特點是“現進后出”,
堆疊的有關操作:
| 例子 | 說明 |
|---|---|
| stackq; | 定義堆疊,Type為資料型別 |
| s.push(item); | 把item防到堆疊頂 |
| s.top(); | 回傳堆疊頂的元素,但不會洗掉 |
| s.size(); | 回傳堆疊中元素的個數 |
| s.empty(); | 判斷堆疊是否為空 |
例題:翻轉字串
例如,輸入"olleh !dlrow",輸出"hello world!";
代碼如下:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
char ch;
scanf("%d",&n);getchar();
while(n--)
{
stack<char>s;
while(true)
{
ch=getchar();//一次讀入一個字符
if(ch==' '||ch=='\n'||ch==EOF)
{
while(!empty())
{
printf("%c",s.pop());//輸出堆疊頂
s.pop();//清除堆疊頂
}
if(ch=='\n'||ch==EOF)break;
printf(" ");
}
else s.push(ch);//入堆疊
}
printf("\n");
}
}
例題:簡單計算器(逆波蘭運算式)
——數字先入堆疊,+號就把數字入堆疊,-號就把數字加個負號入堆疊,如果是乘號就取出堆疊頂元素乘上去,除號同理,最后計算堆疊中所有數字的和就是答案了,
代碼如下:
#include<cstdio>
#include<stack>
#include<algorithm>
int main()
{
double n,m;
char c;
while(~scanf("%lf",&n))
{
c=getchar();
if(c=='\n'&&n==0)break;
stack<double>s;
s.push(n);
scanf("%c",&c);
while(~scanf("%lf",&n))
{
if(c=='*')
{
m=s.pop();
m*=n;
s.pop();
s.push(m);
}
if(c=='/')
{
m=s.pop();
m/=n;
s.pop();
s.push(m);
}
if(c=='+')
s.push(n);
if(c=='-')
s.push(0-n);
if(getchar()=='\n')
break;
c=getchar();
}
double sum=0;
while(s.empty())
{
sum+=s.top();
s.pop();
}
printf("%.2lf\n",sum);
}
return 0;
}
佇列和queue
特點:先進先出
佇列的有關操作:
| 例子 | 說明 |
|---|---|
| queueq; | 定義佇列,Type為資料型別 |
| q.push(item); | 把item放進佇列 |
| q.front(); | 回傳隊首元素,但不會洗掉 |
| q.pop(); | 洗掉隊首元素 |
| q.back(); | 回傳隊尾元素 |
| q.size(); | 回傳元素個數 |
| q.empty(); | 檢查佇列是否為空 |
例題:ACboy needs your help again!
Problem Description
ACboy was kidnapped!!
he miss his mother very much and is very scare now.You can’t image how dark the room he was put into is, so poor 😦.
As a smart ACMer, you want to get ACboy out of the monster’s labyrinth.But when you arrive at the gate of the maze, the monste say :" I have heard that you are very clever, but if can’t solve my problems, you will die with ACboy."
The problems of the monster is shown on the wall:
Each problem’s first line is a integer N(the number of commands), and a word “FIFO” or “FILO”.(you are very happy because you know “FIFO” stands for “First In First Out”, and “FILO” means “First In Last Out”).
and the following N lines, each line is “IN M” or “OUT”, (M represent a integer).
and the answer of a problem is a passowrd of a door, so if you want to rescue ACboy, answer the problem carefully!
Input
The input contains multiple test cases.
The first line has one integer,represent the number oftest cases.
And the input of each subproblem are described above.
Output
For each command “OUT”, you should output a integer depend on the word is “FIFO” or “FILO”, or a word “None” if you don’t have any integer.
Sample Input
4
4 FIFO
IN 1
IN 2
OUT
OUT
4 FILO
IN 1
IN 2
OUT
OUT
5 FIFO
IN 1
IN 2
OUT
OUT
OUT
5 FILO
IN 1
IN 2
OUT
IN 3
OUT
Sample Output
1
2
2
1
1
2
None
2
3
Source
2007省賽集訓隊練習賽(1)
Recommend
lcy
模擬堆疊和佇列,堆疊是FILO,佇列是FIFO,
代碼如下:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,temp;
cin>>t;
while(t--)
{
string str,str1;
queue<int>Q;
stack<int>S;
cin>>n>>str;
if(str=="FIFO")//佇列
{
cin>>str1;
if(str1=="IN")
{
cin>>temp;
Q.push(temp);
}
if(str1=="OUT")
{
if(Q.empty())cout<<"None"<<endl;
else
{
cout<<Q.front()<<endl;
Q.pop();
}
}
}
else
{
cin>>str1;
if(str1=="IN")
{
cin>>temp;
S.push(temp);
}
if(str1=="OUT")
{
if(S.empty())cout<<"None"<<endl;
else
{
cout<<S.pop()<<endl;
S.pop();
}
}
}
}
}
優先佇列和priority_queue
優先佇列:優先級高的先出隊,
佇列和排序的完美結合,不僅可以存盤資料,還可以將這些資料按照設定的規則進行排序,
每次的push和pop操作,優先佇列都會動態調整,把優先級最高的元素放在前面,
priority_queue<int,vector,lessq>
priority_queuei;
priority_queued;
q.top();//回傳具有最高優先級的元素,但不洗掉該元素
q.pop();//洗掉優先級最高的元素
q.push(item);//插入新元素
優先佇列具有佇列的所有特性,包括基本操作,只是在這基礎上添加了內部的一個排序,它本質是一個堆實作的
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int>q;
int main()
{
q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);
while(!q.empty())
{
printf("%d "q.top());
q.pop();
}
}
輸出結果將會是從大到小排序的,

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,less<int> >p;
priority_queue<int,vector<int>,greater<int> >q;
int a[5]={10,12,14,6,8};
int main()
{
for(int i=0;i<5;i++)
p.push(a[i]),q.push(a[i]);
printf("less<int>:");
while(!p.empty())
printf("%d",p.top()),p.pop();
printf("\ngreater<int>:");
while(!q.empty())
{
printf("%d "q.top()),q.pop();
}
}

STL中,優先佇列是用二叉堆實作的,往佇列中push入一個數或pop一個數,復雜度是O(logn),
例:圖論的Dijkstra演算法的程式實作,用STL的優先佇列能極大地簡化代碼,
習題:hdu 1873 看病要排隊
題目描述
看病要排隊這個是地球人都知道的常識,
不過經過細心的0068的觀察,他發現了醫院里排隊還是有講究的,0068所去的醫院有三個醫生(汗,這么少)同時看病,而看病的人病情有輕重,所以不能根據簡單的先來先服務的原則,所以醫院對每種病情規定了10種不同的優先級,級別為10的優先權最高,級別為1的優先權最低,醫生在看病時,則會在他的隊伍里面選擇一個優先權最高的人進行診治,如果遇到兩個優先權一樣的病人的話,則選擇最早來排隊的病人,
現在就請你幫助醫院模擬這個看病程序,
輸入
輸入資料包含多組測驗,請處理到檔案結束,
每組資料第一行有一個正整數N(0<N<2000)表示發生事件的數目,
接下來有N行分別表示發生的事件,
一共有兩種事件:
1:“IN A B”,表示有一個擁有優先級B的病人要求醫生A診治,(0<A<=3,0<B<=10)
2:“OUT A”,表示醫生A進行了一次診治,診治完畢后,病人出院,(0<A<=3)
輸出
對于每個"OUT A"事件,請在一行里面輸出被診治人的編號ID,如果該事件時無病人需要診治,則輸出"EMPTY",
診治人的編號ID的定義為:在一組測驗中,"IN A B"事件發生第K次時,進來的病人ID即為K,從1開始編號,
樣例輸入 Copy
7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1
樣例輸出 Copy
2
EMPTY
3
1
1
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
struct Node{
int id;
int p;
int doc;
}node[10010];
struct cmp{
bool operator()(Node a, Node b){
if(a.p!=b.p)//如果優先權相等不變動,坑點在這里
return a.p < b.p;//因為仿函式和sort相反所以這里是從大到小排序
else return a.id > b.id;
}
};
priority_queue<Node,vector<Node>,cmp> q,q1,q2;
int main(){
ios::sync_with_stdio(false);
int n;
string str;
while(cin>>n){
while(!q.empty()){
q.pop();
}
while(!q1.empty()){
q1.pop();
}
while(!q2.empty()){
q2.pop();
}
int cnt = 1;
for(int i = 0; i < n; i++){
cin>>str;
if(str=="IN"){
cin>>node[i].doc>>node[i].p;
node[i].id = cnt++;
if(node[i].doc==1)
q.push(node[i]);// 1號醫生
else if(node[i].doc==2)
q1.push(node[i]);// 2號醫生
else if(node[i].doc==3)
q2.push(node[i]);// 3號醫生
}else{
int num;
cin>>num;
if(num==1){
if(q.empty()){
cout<<"EMPTY"<<endl;
continue;
}
Node node1 = q.top();
cout<<node1.id<<endl;
q.pop();
}
else if(num==2){
if(q1.empty()){
cout<<"EMPTY"<<endl;
continue;
}
Node node1 = q1.top();
cout<<node1.id<<endl;
q1.pop();
}else if(num==3){
if(q2.empty()){
cout<<"EMPTY"<<endl;
continue;
}
Node node1 = q2.top();
cout<<node1.id<<endl;
q2.pop();
}
}
}
}
return 0;
}
map:
例題:shopping
題意:
女孩dandelion經常去購物,她特別喜歡一家叫“memory”的商店,
由于春節快到了,所有商店的價格每天都在上漲,她想知道這家商店每天的價格排名,
Input:
第一行是數字n(n <= 10000),代表商店的數量, 后面n行,每行有一個字串
(長度小于31,只包含小寫字母和大寫字母)表示商店的名稱, 然后一行是數字m(1 <= m <= 50),
表示天數, 后面有m部分,每部分有n行,每行是數字s和一個字串p,表示商店p在這一天漲價s,
Output:
包含m行,第i行顯示第i天后店鋪“memory”的排名,排名的定義為:
如果有t個商店的價格高于“memory”,那么它的排名是t + 1,
代碼如下:
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main(){
map<string,int>m;
int n,M;
int s;
string store;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>store;
m[store]=0;
}
cin>>M;
for(int i=0;i<M;i++){
for(int j=0;j<n;j++){
cin>>s>>store;
m[store]+=s;
}
int k=0;
for(map<string,int>::iterator it=m.begin();it!=m.end();it++)
if(it->second>m["memory"])k++;
cout<<k+1<<endl;
}
}
return 0;
}
next_permutation
1.next_permutation():求“下一個”排列組合
2.例如三個字符{a,b,c}組成的序列,next_permutation()能按字典序回傳6個組合:abc,acb,bac,bca,cab,cba,
3.回傳值:如果沒有下一個排列組合,回傳false,否則回傳true,每執行next_permutation()一次,會把新的排列放到原來的空間里,
例題:
給定n個數字,從1到n,要求輸出第m小的序列
輸入:
數字n和m組成,1<=n<=1000,1<=m<=10000
輸出:
輸出第m小的序列
代碼如下:
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int a[1001];
int main(){
int n,m;
while(cin>>n>>m){
for(int i=1;i<=n;i++)
a[i]=i;
int b=1;
do{
if(b==m)break;
b++;
}while(next_permutation(a+1,a+n+1));
for(int i=1;i<n;i++)
cout<<a[i]<<" ";
cout<<a[n]<<endl;
}
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/319719.html
標籤:其他
上一篇:優先級佇列-堆【資料結構】
下一篇:一個小菜鳥的開始
