这道题一看到的思路是分治：每次找到最低点，每个坑相应地填最低点的高度，然后divide为最低点左右两部分按此思路继续divide，直到 l>r 时结束。 分治的做法按提供的样例可以过，但是分治的时间复杂度在[nlogn, n^2]之间，n最大为1e5规模，如果卡了 n2 的样例会TLE。 分治代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5+3; int a[maxn]; int ans; void divide(int l,int r) { if(l>r) return; int minn=0x3f3f3f3f; int pos=l; for(int i=l;i<=r;i++) { if(a[i]<minn) { minn=a[i]; pos=i; } } for(int i=l;i<=r;i++) { a[i]-=minn; } ans+=minn; divide(l,pos-1); divide(pos+1,r); } int main() { int i,j; int n,m; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } ans=0; divide(1,n); printf("%d\n",ans); return 0; }其实还有贪心的解法：对于各个坑，当大的坑被填时，小的坑肯定也顺带填掉才能使总花费最少，当小坑填完后，大坑还要填(大坑高度-小坑高度)次。因此有：设一个值为0的0号坑，从0号坑开始，若其后的坑的高度比当前坑的高度高，ans加上两者高度差，直到遍历完所有坑，时间复杂度为O(n)。(设定0号坑可行是因为肯定至少要填1号坑的高度次) 贪心代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5+3; int a[maxn]; int main() { int i,j; int n,m; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } a[0]=0; int ans=0; for(i=1;i<=n;i++) { if(a[i]>a[i-1]) ans+=a[i]-a[i-1]; } printf("%d\n",ans); return 0; }