STL（二）——vector

一.vector容器

① 动态数组，从末尾能快速插入与删除，直接访问任何元素。
② 一个摸板类，能存放任何类型的对象。
③ Vector作为函数的参数或者返回值时，需要注意它的写法：
double Distance(vector<int>&a, vector<int>&b) 其中的 “&” 绝对不能少！

</int></int>

二.vector的基本操作

(1)创建vector对象，vector<int> vec;</int>

(2)尾部插入数字：vec.push_back(a);

(3)使用下标访问元素，cout<<vec[0]<<endl;

(4)使用迭代器访问元素.

vector<int>::iterator it;

for (it = vec.begin(); it != vec.end(); it++)
    cout << *it << endl;

(5)插入元素： vec.insert(vec.begin()+i, a); //在第i+1个元素前面插入a;

(6)删除元素： vec.erase(vec.begin()+2); //删除第3个元素
vec.erase(vec.begin()+i,vec.end()+j); //删除区间[i,j-1];区间从0开始

(7)向量大小:vec.size();

(8)清空:vec.clear();

(9)使用reverse将元素翻转：
reverse(vec.begin(),vec.end());//将元素翻转，即逆序排列！

(10)使用sort排序：
sort(vec.begin(), vec.end());(默认是按升序排列,即从小到大).

可以通过重写排序比较函数按照降序比较，如下：

bool cmp(const int &a, const int &b) {
    return a > b;
}
sort(vec.begin(), vec.end(), cmp)

三.vector应用

HDOJ4841-圆桌问题

Problem Description
圆桌上围坐着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

BGGB

是一个典型的约瑟夫环问题，在这里vector可模拟圆桌，算法思想是让vector只存储好人的编号，不在vector内的编号则全为坏人。

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
int main() {
  vector<int> a;
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    a.clear();
    for (int i = 0; i < 2*n; i++) {//初始化 
      a.push_back(i);
    }
    int temp = 0;//记录当前位置 
    for (int i = 0; i < n; i++) {//踢出n个人 
      temp = (temp+m-1)%a.size();//圆桌是个环，取余处理 
      a.erase(a.begin() + temp);//赶走坏人，size-1 
    }
    int count = 0;
    for (int i = 0; i < 2*n; i++) {//打印座位 
      if ((i%50 == 0) && i) cout << endl;//遇到50换行 
      if (count < a.size() && a[count] == i) {//vector存的都是好人，将size个元素全部输出后，剩余皆为坏人 
        cout << "G";
        count++;
      } else {
        cout << "B";
      }
    }
    cout << endl << endl;//留空行处理 
  }
}