为什么ACMer用数组而不用vector这样的动态数组？

首先vector和map等STL工具，由于封装以及提高了适应性（模板），效率是比你手写的低的，再加上POJ的编译器比较陈旧，编译器优化上做的不够好。因此STL必须慎重使用。另外对于一下两段代码。

inta[100005];

for(inti=0;i<n;++i)

cin>>a[i];

以及

vector<int>a;

for(inti=0;i<n;++i)

{

intx;

cin>>x;

a.push_back(x);

}

后者占用的时间其实比前面多很多。因为vector的动态长度的实现就是，一开始的空间是1(2^0)，插入一个元素，再插入一个元素，没位置？好，new2个空间(2^1),然后把第一个元素拷贝进去，把要插入的元素放在后面。再插入一个元素，没位置？好，new4个空间(2^2)，然后把前两个元素拷贝进去，把要插入的元素放在第三个位置，再插入一个元素，再插入一个元素，没位置？好，new8个空间(2^3)，然后把前四个元素拷贝进去，把要插入的元素放在第五个位置....

所以在不停地push_back的过程中，其实系统在不停地进行分配空间，拷贝，释放。。。大家也知道，拷贝不可能O(1)的啊~

因此一个比较有效的方法是把vector当成一个静态数组使用。

vector<int>a(n);//让这个vector一开始就有n个空间

for(inti=0;i<n;++i)

{

intx;

cin>>x;

a[i]=x;//注意不能push_back了，否则就是在n+1的地方开始了。

}

首先讲讲vector在C++STL中的实现方式。

vector在STL中通过一段连续的地址储存数据，当这段内存用完后，vector会申请一段更长的内存（通常是两倍），然后把原来的数据copy过去，并释放之前的内存。

这个操作的时间复杂度仍是均摊O(1)的，和数组一样。但是因为copy和申请内存、释放内存等操作，常数会比数组大一些。同时，STL的适应性等也对常数有一些影响。

因为ACM竞赛有时间限制，因此选手大多会注重代码的时间效率，有时候也会注意常数优化，因此在一些可以用数组的场合，会尽量使用数组而不是vector。

至于map，在C++STL中是使用红黑树（一种平衡树）实现的。因此，map的单次操作的时间复杂度为O(logN)，其中N为map中的元素个数。这比数组的O(1)时间复杂度要更劣一些，这也可能是你TimeLimitExceeded的原因。

在实现代码之前，不妨可以计算一下时间复杂度，估计一下时间复杂度的常数，然后选择实现的方法。

在时间限制允许的情况下，为了方便，我也会选择vector、map等STLContainer。但是有时候如果时间限制比较紧，那么我会选择常数较小的实现方法。

希望对你有帮助。