题目大意如下：(其他描述被我略过，只剩下核心问题)
有一堵长度为n块砖的墙，现在要把墙拆掉，每次拆掉最外围的砖块(不太好描述，下面有样例解释)，
问要拆几次才可以把墙拆掉？

输入格式：
第1行输入墙的长度n（1≤n≤10^5）
第2行输入n个数Mi，分别对应每个单位长度墙的高度（1≤Mi≤10^9）

输出格式：
输出次数m

输入样例：
10
3 1 2 4 6 5 2 1 4 2

输出样例：
4

样例解释：
见图：
第1次拆掉的打叉
第2次拆掉的打三角
第3次拆掉的打井号
第4次拆掉的打圈
总共需要4次

谢谢你提供的思路，毫无疑问，在数据规模较小的情况下可以这样写。
但是现在面临一个问题就是Mi能取到10的9次方，这个思路就不成立了。是吧？

嗯，我也研究了半天，但是解决不了超时的问题，看到这个数据规模我人都傻了。

高手就是不一样。给你点个赞。我还没有细看你的代码，我今早也想了个方案，刚刚做出来提交过了，哈哈。。
以下附上我朴素的思路以及代码：

思路：
定义一个数组dp[],存放每一列最底下一块砖第几次被拆掉。
这个数值被2种情况影响
1、头顶上的砖被拆掉了，就轮到最后一块砖了
2、左边或右边一列最后一块砖被拆掉了，也轮到此列的砖被拆

一开始我们定义一个结构体a，保存输入数据，并保存下标(因为我下面用到了排序)
dp[]数组初始化为：min{当前列砖的数量，当前列到两个边界的最小距离};
为什么要取到边界的最小距离呢？因为每拆一次，边界那两列砖必定被拆掉。
然后对结构体数组排序。从砖数量少的列数开始处理，更新两边的状态，详细的处理看代码吧。

#include <cstdio>
#include <algorithm>
#define MAXN 100000
using namespace std;
struct Data
{
    long long bricks;//存放数据(每一列砖的高度)
    int index;//存放数组下标
};
struct Rule//按砖的高度，从小到大排序
{
    bool operator()(const Data &s1, const Data &s2)
    {
        if (s1.bricks < s2.bricks)
            return true;
        else
            return false;
    }
};
Data a[MAXN+10];
long long dp[MAXN+10];
int main(void)
{
    int n;
    long long i;
    scanf("%d", &n);//墙的长度
    for (i=1; i<=n; ++i)
    {
        scanf("%lld", &a[i].bricks);//输入每一类砖的高度
        dp[i] = a[i].bricks;
        a[i].index = i;//保存下标
    }
    //dp[]初始化
    for (i=1; i<=n/2; ++i)
        dp[i] = min(dp[i], i);
    for (i=n; i>n/2; --i)
        dp[i] = min(dp[i], n+1-i);
    //从小到大排序
    sort(a+1, a+n+1, Rule());
    int Max=0;
    for (i=1; i<=n; ++i)
    { 
        //更新左边的dp[]
        if (dp[a[i].index]+1<dp[a[i].index-1])
            dp[a[i].index-1] = dp[a[i].index]+1;
        //更新右边的dp[]
        if (dp[a[i].index]+1<dp[a[i].index+1])
            dp[a[i].index+1] = dp[a[i].index]+1;
    }
    //找出dp[]中最大的一个
    for (i=1; i<=n; ++i)
    {
        if (dp[i]>Max)
            Max = dp[i];
    }
    printf("%d", Max);//输出
    return 0;
}

妙啊，两种方法都很好。。只是为什么我的电脑跑不出结果。

[此贴子已经被作者于2018-11-23 19:49编辑过]

嗯，原来要等这么久。谢谢了。