哇咔咔　renew你做这个这么勤快 -_-

[quote][quote]哎，最后没有输出\n，除了最后一个，其余结果全部算错。

但是题目没有说要"%d\n"或者cout<<n<<endl啊[/quote]

并不是没有换行的问题。实际上是您程序上的缺陷，如果用VC编译再手工去评测“表面上”是不会有问题的。G＋＋也一样。

while(++i <= n)
    {
        if(stack.empty() || h[i] < stack.back().height) ------请注意这边
            stack.push_back(_elem(i, h[i]));
        else
        {
            while(!stack.empty() && (i==n || h[i]>=stack.back().height))
            {
                total += (i-stack.back().index-1);
                stack.pop_back();
            }
            if(i < n) stack.push_back(_elem(i, h[i]));
        }
    }

在那里有个小问题，呵呵，自己找找，我就不讲出来了。加了一条语句后，您的程序就可以得满分了！
因为程序效率的因素（其实是用了STL，动态开辟内存等），虽然程序可以得满分，但很遗憾，您程序还是不能进入第二轮评测。

这是新的评测结果。（没法发图片，请将就着看吧-,-）

测试点    使用内存    运行时间    结果    得分
1    504 KB    296 MS    Accept    10
2    504 KB    312 MS    Accept    10
3    500 KB    265 MS    Accept    10
4    940 KB    203 MS    Accept    10
5    1328 KB    218 MS    Accept    10
6    516 KB    281 MS    Accept    10
7    640 KB    156 MS    Accept    10
8    940 KB    328 MS    Accept    10
9    940 KB    296 MS    Accept    10
10    504 KB    234 MS    Accept    10[/quote]

知道了，上下条件不一致，应该都是

(!stack.empty() && ([b]i==n[/b] || h[i]>=stack.back().height)

原先只是++i<n，后来改为++i<=n，结果上面那一行没有改。

我写程序就是这样，总是改来改去，但是总是不能保证逻辑一致性。直到看见bug才会意识到问题。

一开始把i==n的情况挪到后面处理也就ok了，就是后面多一个while循环，但是我写程序不喜欢写重复的代码段，所以直接把while循环合并，结果上面的if条件没改。

然后STL在debug模式很慢，但是release很快，至于快多少，得看具体情况。我写的C++预处理器（使用了大量的模板，包括stl）在debug模式生成15000+行的代码（include vector、algorithm、list、map这些比较肥的头文件）需要2s-3s左右，但是release模式只需要不到1s就可以完成。

STL的四大容器（vector、list、set、map）中，set和map的查找速度最快，采用排序树，复杂度log2N，但是插入操作比list慢，比vector的中间插入快。

vector的尾部操作最快，但是中间插入和删除最慢。

list所有操作速度都很一般。

这些都是数据结构本身决定的，让你写一个类似的结构最多也就在debug模式下占优势，在release模式下快不了多少。

要想提高stl的容器速度，最好的办法是改写allocator，我所能想到的最快的allocator估计是页计数：申请一大块固定长度的内存作为一页，为该页设置一个指针和一个计数。当分配内存时通过指针计算该页剩余空间，如果够用就计数加1，指针移动n即可；如果空间不够，则再申请一块大的。当回收空间时，找到指针属于哪个页面，该页面计数减1，如果减到0则删除该页，也可以预留一页当缓冲，避免抖动现象。这个allocator的限制是一次分配的空间不能大于一页。页面越大，效果越好。

vector的速度瓶颈还在于realloc的速度问题。通常realloc需要内存拷贝，从而大幅度的降低效率。

为该问题的解决方法是考虑到程序中只有一个vector，那么专门为该vector分配一大片空间，返回首指针，realloc时只要需求的内存不超过实际空间大小，直接返回该指针即可，无需内存拷贝和其他附加操作。这样的话，该vector的速度应该和足够大小的数组效率一样。

一般编程比赛懒得去费心思了，看看结果对不对也就OK了。

[quote]再次对楼主的专业和细心表示钦佩！赞一个！[/quote]
[em2]

[quote][quote][quote]综合大家的成果改进了一下,应该是最快得了^^

long CountShort(long n, long *height)
{
    long cnt[50001]={0}, i, j;
    long sum = 0;
    //cnt[i]储存i与右边不矮于他的第一个j的序号差(j-i)
    for(cnt[n-1] = 1, i = n-2; i >= 0; i--)
    {
        for(j = i+1; j < n && height[i] > height[j]; j += cnt[j]);
        cnt[i] = j-i;
        sum += cnt[i]-1;
    }
    return sum;
}[/quote]

long cnt[50001]={0};光是这步初始化就慢了－，－[/quote]


这个慢不慢到是无所谓,关键是long cnt[50001]占用了50001 * sizeof(long),
至少200k的栈空间,受得了么[/quote]
没有问题的

SonicLing
你要效率的话就直接用数组和指针进行操作吧
用C++封装过的东西都快不到哪里去

呵呵
我做的 不好啊 
以后要加油啊 
辛苦楼主了啊

真的比赛的时候，能有效的用STL也是很好的，AC数目更加重要，AC的效率比程序的效率重要～

我看了下结果，楼主真认真～辛苦了！

[quote]SonicLing
你要效率的话就直接用数组和指针进行操作吧
用C++封装过的东西都快不到哪里去[/quote]


虽然没直接用数组和指针快，但是也很快。比赛用STL拿第一肯定没戏，不过拿前面几名还是有希望。程序可读性和效率兼顾。我是没指望拿第一，参与，参与。