51Nod 1276 岛屿的数量

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int MAXN = 5e4+5;
 9 struct node
10 {
11     int pos, val;
12 };
13 node a[MAXN], q[MAXN];
14 
15 bool cmp(node a, node b)
16 {
17     return a.val < b.val;
18 }
19 
20 bool vis[MAXN];
21 int ans[MAXN];
22 
23 int main()
24 {
25     int N, Q;
26     while(~scanf("%d%d",&N,&Q))
27     {
28         memset(vis, 0, sizeof(vis));    //没被淹没
29         for(int i=0; i<N; i++)
30         {
31             scanf("%d",&a[i].val);
32             a[i].pos = i;
33         }
34         for(int i=0; i<Q; i++)
35         {
36             scanf("%d",&q[i].val);
37             q[i].pos = i;
38         }
39         sort(a, a+N, cmp);
40         sort(q, q+Q, cmp);
41         int sum = 1, j = 0 ;
42         for(int i=0; i<Q; i++)
43         {
44             while(a[j].val <= q[i].val && j<N)
45             {
46                 //判断是不是第一个点
47                 if(a[j].pos == 0)
48                 {
49                     if(vis[1])      //被淹没
50                         sum--;
51                 }
52                 //判断是不是最后一个点
53                 else if(a[j].pos == N-1)
54                 {
55                     if(vis[N-2])
56                         sum--;
57                 }
58                 else
59                 {
60                     if(vis[a[j].pos-1] && vis[a[j].pos+1])//山峰
61                         sum--;
62                     else if(!vis[a[j].pos-1] && !vis[a[j].pos+1])//山谷
63                         sum++;
64                 }
65                 vis[a[j].pos] = 1;      //标记被淹没
66                 j++;
67             }
68             ans[q[i].pos] = sum;
69         }
70         for(int i=0; i<Q; i++)
71             printf("%d
",ans[i]);
72     }
73     return 0;
74 }