题目描述 每当下雨时，FJ的牧场都会进水。由于牧场地面高低不平，被水淹没的地方不是很统一，形成一些岛屿。 FJ的牧场可描述成一个一维的地形图，由N(1 <= N <= 100,000)个彼此相连的柱状的高度值组成。高度值为H(1)…H(n)。假定这个地形图的两端有两条无限高的墙围着。 当雨一直下时，地形图上最低的区域先被水淹没，形成一些不相邻的岛屿。一旦水面高度到达一个区域的高度，则认为这个区域被淹没。 左图，在当前水面时，有4个岛屿。右图，在水面升高后，剩下2个岛屿。显然，最终所有的区域都会沉入水面。 算出当雨从开始下到最后所有岛屿沉入水中，最多时可形成多少个岛屿。
分析 这个涉及到贪心（应该，不知道判断准不准） 经黄家旺标程和祝子扬指点后做出（友情链接那两位） 步骤一：将岛屿高度，岛屿下标（也不知道怎么形容了）搞些预处理 步骤二：因为岛屿高度后面要用，所以用c数组备份快排（排的其实是岛屿下标） 步骤三：按洪水进度，从高到低循环 【这里有两种情况：周围岛屿比中间这一个枚举到的高，那么岛屿数量加1；中间这个枚举到的比周围高，那么岛屿就少了一个（-1）】 大概就这样啦
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,a[100001],b[100001],c[100001],i,j,s,m; void qs(int l,int h) { int i=l,j=h,mid=c[(l+h)/2],t; do { while (c[i]<mid) i++; while (c[j]>mid) j--; if (i<=j) { t=c[i];c[i]=c[j];c[j]=t; t=a[i];a[i]=a[j];a[j]=t; i++;j--; } } while (i<=j); if (i<h) qs(i,h); if (l<j) qs(l,j); } int main() { freopen("islands.in","r",stdin); freopen("islands.out","w",stdout); scanf("%d",&n); j=0; for (i=1;i<=n;i++) { scanf("%d",&s); if (s!=b[j]) { j++; b[j]=s; a[j]=j; } } memcpy(c,b,sizeof(b)); qs(1,n); s=1; for (i=1;i<=n;i++) { if (b[a[i]+1]>b[a[i]]&&b[a[i]-1]>b[a[i]]) s++; else if (b[a[i]+1]<=b[a[i]]&&b[a[i]-1]<=b[a[i]]) s--; if (s>m) m=s; } printf("%d",m); return 0; }