排序+逆向思维 ACdream 1205 Disappeared Block

 1 /*
 2     从大到小排序，逆向思维，从最后开始考虑，无后向性
 3     每找到一个没被淹没的，对它左右的楼层查询是否它是孤立的，若是++，若不是--
 4     复杂度 O(n + m)，还以为 O(n^2)吓得写了一半就不写了
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <iostream>
 9 #include <algorithm>
10 #include <map>
11 #include <set>
12 #include <string>
13 using namespace std;
14 
15 const int MAXN = 1e6 + 10;
16 const int INF = 0x3f3f3f3f;
17 struct Hight
18 {
19     int val, id;
20 }h[MAXN];
21 int q[MAXN];
22 int vis[MAXN];
23 int ans[MAXN];
24 
25 bool cmp(Hight a, Hight b)
26 {
27     return a.val > b.val;
28 }
29 
30 int main(void)        //ACdream 1205 Disappeared Block
31 {
32     //freopen ("J.in", "r", stdin);
33 
34     int t;
35     int n, m;
36 
37     scanf ("%d", &t);
38     int cas = 0;
39     while (t--)
40     {
41         memset (vis, 0, sizeof (vis));
42         scanf ("%d%d", &n, &m);
43         for (int i=1; i<=n; ++i)
44         {
45             scanf ("%d", &h[i].val);
46             h[i].id = i;
47         }
48         for (int i=1; i<=m; ++i)    scanf ("%d", &q[i]);
49 
50         sort (h+1, h+1+n, cmp);
51 
52         int cnt = 0;    int res = 0;
53         for (int i=1, j=m; j>=1; --j)
54         {
55             for (; i<=n; ++i)
56             {
57                 if (h[i].val <= q[j])    break;
58                 int pos = h[i].id;
59                 vis[h[i].id] = 1;
60                 if (!vis[pos-1] && !vis[pos+1])    res++;
61                 if (vis[pos-1] && vis[pos+1])    res--;
62             }
63             ans[j] = res;
64         }
65         printf ("Case #%d: ", ++cas);
66         for (int i=1; i<=m; ++i)    printf ("%d%c", ans[i], (i==m) ? ‘\n‘ : ‘ ‘);
67     }
68     
69 
70     return 0;
71 }
72 
73 /*
74 Case #1: 1 1 2 
75 Case #2: 1 2 1 1 0
76 */