题目来源： Codility
基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题
有N个岛连在一起形成了一个大的岛屿，如果海平面上升超过某些岛的高度时，则这个岛会被淹没。原本的大岛屿则会分为多个小岛屿，如果海平面一直上升，则所有岛都会被淹没在水下。
给出N个岛的高度。然后有Q个查询，每个查询给出一个海平面的高度H，问当海平面高度达到H时，海上共有多少个岛屿。例如：
岛屿的高度为：{2, 1, 3, 2, 3}, 查询为：{0, 1, 3, 2}。
当海面高度为0时，所有的岛形成了1个岛屿。
当海面高度为1时，岛1会被淹没，总共有2个岛屿{2} {3, 2, 3}。
当海面高度为3时，所有岛都会被淹没，总共0个岛屿。
当海面高度为2时，岛0, 1, 3会被淹没，总共有2个岛屿{3} {3}。
Input
第1行：2个数N, Q中间用空格分隔，其中N为岛的数量，Q为查询的数量(1 <= N, Q <= 50000)。
第2 - N + 1行，每行1个数，对应N个岛屿的高度(1 <= A[i] <= 10^9)。
第N + 2 - N + Q + 1行，每行一个数，对应查询的海平面高度(1 <= Q[i] <= 10^9)。
Output
输出共Q行，对应每个查询的岛屿数量。
Input示例
5 4
2
1
3
2
3
0
1
3
2
Output示例
1
2
0
2
脑洞题。。
#include <algorithm>
#include <cstdio>
#define N 50005
using namespace std;
struct node
{
int id,ans,h;
}Q[N];
struct nodee
{
int id,h;
bool operator<(nodee a)const
{
return h<a.h;
}
}A[N];
bool cmp(node a,node b)
{
return a.h<b.h;
}
bool comp(node a,node b)
{
return a.id<b.id;
}
int n,q;
bool ym[N];
int Main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;++i) scanf("%d",&A[i].h),A[i].id=i;
sort(A+,A++n);
for(int i=;i<=q;++i)
{
scanf("%d",&Q[i].h);
Q[i].id=i;
}
sort(Q+,Q++q,cmp);
int j=,sum=;
for(int i=;i<=q;++i)
{
while(A[j].h<=Q[i].h&&j<=n)
{
if(A[j].id==) {if(ym[]) sum--;}
else if(A[j].id==n) {if(ym[n-]) sum--;}
else
{
if(ym[A[j].id-]&&ym[A[j].id+]) sum--;
else if(!ym[A[j].id-]&&!ym[A[j].id+]) sum++;
}
ym[A[j].id]=;
j++;
}
Q[i].ans=sum;
}
sort(Q+,Q++q,comp);
for(int i=;i<=q;++i) printf("%d\n",Q[i].ans);
return ;
}
int sb=Main();
int main(int argc,char *argv[]){;}