1648_向量插入元素

定义向量数据结构如下：

#define  MAX_SIZE  100000

/// >节点基础数据类型

typedef struct  Node {
     int id;        ///员工编号，唯一
     char  name[20];  /// 员工名字
} mytype;

/// 简陋定义方式，局限：只能定义一个vector

mytype mydata[ MAX_SIZE ];   /// 向量元素存放的数组

int _size;   /// 向量元素的实际个数

对该向量执行K次插入一个元素的操作  int insert ( int r, mytype e ) ：在秩r的位置插入元素e 。

最后遍历输出该向量。

本题不考虑向量的增容问题。

建议：初始化向量为空。

第一行是一个正整数K ( 1 < K < 100000 ) ，表示有K次插入操作。

接下来是K行，每行是一个整数 r 和 一个整数id 和 一个字符串str ，分别表示插入的位置r 和 员工编号 和 员工姓名。

0 ≤ r < 100000 。当 r 大于 _size 时，则把元素放在向量末尾 。

员工姓名字符串str 不含空格、1 < |str| < 20 。

以 秩 从0到 _size -1 的顺序输出向量，每行一个元素：先输出员工编号id，再输出员工名字。

5
0 1 Tom
0 2 Jack
3 3 Alice
1 4 Bob
3 5 Apple

2 Jack
4 Bob
1 Tom
5 Apple
3 Alice

讨论：插入元素操作中，后移一个元素的消耗太大。当插入操作频繁时，总耗时很大。因此，题目的数据量不得不从一百万降低到十万。

实验结果，一百万的数据量，加上执行一百万次的插入操作，可能需要十几到几十分钟。