[数据结构与算法]（超详细）算法学习：STL和基本数据结构

STL容器
vector
栈
队列
链表
set
map
sort函数
next_permulation函数

容器
1.顺序式容器：vector,list,deque,queue,priority_queue,stack等；
2.关联式容器：set，multiset，map，multimap等

vector

vector容器能存放任何类型的对象：

圆桌上围坐着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
栈：基本的数据结构之一，特点是“现进后出”。

栈的有关操作：

例题：翻转字符串
例如，输入"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
特点：先进先出
队列的有关操作：

例题：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;
}