vector打印锯齿矩阵

一、题目

锯齿矩阵是指每一行包含的元素个数不尽相同的矩阵，比如

3 5 2 1 6
2 3 4
1 6 2 7

读入若干对整数（x,y），表示在第x行的末尾加上一个元素y。输出最终的锯齿数组。初始时矩阵为空。

输入格式

第一行输入两个整数n,m(1<=n,m<=10000),其中n表示锯齿矩阵数组的行数，m表示插入元素的总数。

接下来一个m行，每行两个整数x,y(1<=x<=n,0<=y<=10000)，表示在第x行的末尾插入一个元素y。

输出格式

一共输出n行，每行若干个用空格分隔的整数。如果某行没有任何元素，则输出一个空行。

样例输入

3 12
1 3
2 2
2 3
2 4
3 1
3 6
1 5
1 2
1 6
3 2
3 7
1 1

样例输出

3 5 2 6 1 
2 3 4 
1 6 2 7

二、解题思路

在看到这题的第一个想法就是用普通的数组去解决，但又想到要创建一个n*10000的数组，难免会出现问题，又因为本题每一行的元素是根据输入的元素个数变化而变化的，即是一个动态存储的过程，这无疑为vector提供天然的良机，因此本题用vector动态数组来解决，不仅简单（只用二维动态数组即可解决（前者表示行数，后者表示每一行存放的元素）），而且占用的空间内存比普通数组要少得多，采用动态数组为本题的最优解！

三、源码及注释

#include<vector>
using namespace std;
int main()
{
  vector<int> a[10005];//在比赛中常见的定义二维动态数组的方法，方法固定，且效果稳定
  int n, m, x, y;
  cin >> n >> m;
  for (int i=0;i<m;i++)
  {
    cin >> x >> y;
    a[x].push_back(y);//对每一行插入元素
  }
  for (int i=1;i<=n;i++)
  {
    for (int j=0;j<a[i].size(); j++)//遍历二维数组常用的嵌套for循环
    {
      if (j != a[i].size() - 1)
      {
        cout << a[i][j] << ' ';
      }
      else
      {
        cout << a[i][j] << endl;
      }
      //比赛中常用的输出格式技巧（空格、换行）
    }
  }
  return 0;
}