现在的位置: 首页 > 综合 > 正文

ural 1915. Titan Ruins: Reconstruction of Bygones

2013年05月05日 ⁄ 综合 ⁄ 共 807字 ⁄ 字号 评论关闭

翻译:

时间限制:1秒

空间限制: 64MB

对一个栈进行一些操作。详见下。

输入:

第一行一个整数N,操作总数。

接下来N行每行一个操作。若数大于0,代表将该数压栈。 若数等于-1,代表输出并抛弃栈顶元素。若为0,代表将目前栈内所有元素重新压栈。(就是复制一份栈)

输出:

每个-1操作时的栈顶元素。

样例输入:

8

3

4

0

-1

-1

-1

-1

1

样例输出:

4

3

4

3

 1 #include <iostream>
 2 #include <cstdio>
 3 const int MAXN = 1000000 + 10;
 4 int a[2 * MAXN];
 5 using namespace std;
 6 int main()
 7 {
 8     int n;
 9     scanf("%d", &n);
10     int i = 1;                    //i始终指向模拟栈的最后一个元素的下一位置
11     int t;
12     while (n--)
13     {
14         scanf("%d", &t);
15         if (t > 0)
16             a[i++] = t;
17         else if (t == -1)
18             printf("%d\n", a[--i]);
19         else if (t == 0)
20         {
21             if (i - 1 <= n)        //优化1:栈中元素大于剩余操作数就不必复制
22             {
23                 int num = (i - 1) < n ? (i - 1) : n; //优化2:复制的元素不必比剩余操作数多
24                 for (int j = 1; j <= num; ++j)
25                 {
26                     a[i] = a[i-num];
27                     ++i;
28                 }
29             }
30         }
31     }
32     return 0;
33 }

被这一题坑惨了,搞了好长时间,本来我一直用g++4.7.2 c++11提交的,但是总是超时,后来快绝望了,就用vc++提交试试,居然提交了几次都是0.64秒左右AC,又用g++4.7.2提交了几次,0.5秒左右,搞不懂为什么编译器编译后的代码差别那么大。又实验了一些题目,发现用G++4.7.2提交用的时间最快。以后还是用g++4.7.2提交算了。有谁知道原因麻烦告诉我一下,是不是这个c++11最新标准的编译器有缺陷。

抱歉!评论已关闭.