中大sicily9095 soj9095

那个曾经说要在一起永世不分离的人呐

现在又在哪里

在路上

在路上

这题折腾了我好久！第一次做中大的的题目。

这题题目是统计露出水面的岛屿的个数，如果是几个岛屿连在一起的就只算一个，一开始岛屿就是1。

如果一个岛屿的两边都是山的话+1

如果都是水的话-1

其他不用理

思路大概就是这样

注：soj不能用qsort，这个弄得我一直不知道为什么老是显示不能调用函数。所以我用了sort。

题目：http://soj.me/9095

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include <algorithm>
using namespace std;
struct calu
{
 int h;
 int num;
}a[100005],b[100005];  //这里我开了两个数组，a用来存放排序后的，b用来存放初始的
int Max(int a,int b)
{
 if(a>b)return a;
 else return b;
}

bool cmp( struct calu kk ,struct calu kt)
{
 if(kk.h>kt.h)
  return false;
 else
  return true;
}
int main()
{
 int m,i,j,zuo,you,N,flag[100005],fuk,ans;
 while(scanf("%d",&N)!=EOF)
 {
  memset(flag,0,sizeof(flag));
  for(i=0;i<N;i++)
  {
   scanf("%d",&a[i].h);
   a[i].num=i;
   b[i]=a[i];
  }
  sort(a,a+N,cmp);
  a[N].h=1;
  m=1,ans=1;
  for(j=0;j<N;) //一个循环
  {
   fuk=a[j].h;
   while(fuk==a[j].h) //这里是找相同的，一般不可能出现10万个相同的所以不用怕超时
   {
    if(flag[a[j].num]==0)
    {
     flag[a[j].num]=-1;
     you=a[j].num+1; //右标记一直到不同的高度
     while(you<N && flag[you]==0 && b[you].h==fuk)
     {
      flag[you]=-1;
      you++; 
     }
     zuo=a[j].num-1; //左标记一直到不同的高度
     while(zuo<N && flag[zuo]==0 && b[zuo].h==fuk)
     {
      flag[zuo]=-1;
      zuo--;
     }
     if((you>=N || flag[you]==-1) && (zuo<0 || flag[zuo]==-1))  //如果一个岛屿的两边都是水的话-1
                        m--;
     if((you<N && flag[you]==0) && (zuo>=0 && flag[zuo]==0))  //如果一个岛屿的两边都是山的话+1
                        m++;
    }
    j++;
   }
   ans=Max(m,ans);
  }
  printf("%d\n",ans);
 }
 return 0;
}