排序+逆向思维 ACdream 1205 Disappeared Block

 /*

     从大到小排序，逆向思维，从最后开始考虑，无后向性

     每找到一个没被淹没的，对它左右的楼层查询是否它是孤立的，若是++，若不是--

     复杂度 O(n + m)，还以为 O(n^2)吓得写了一半就不写了

 */

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <string>

 using namespace std;

 const int MAXN = 1e6 + ;

 const int INF = 0x3f3f3f3f;

 struct Hight

 {

     int val, id;

 }h[MAXN];

 int q[MAXN];

 int vis[MAXN];

 int ans[MAXN];

 bool cmp(Hight a, Hight b)

 {

     return a.val > b.val;

 }

 int main(void)        //ACdream 1205 Disappeared Block

 {

     //freopen ("J.in", "r", stdin);

     int t;

     int n, m;

     scanf ("%d", &t);

     int cas = ;

     while (t--)

     {

         memset (vis, , sizeof (vis));

         scanf ("%d%d", &n, &m);

         for (int i=; i<=n; ++i)

         {

             scanf ("%d", &h[i].val);

             h[i].id = i;

         }

         for (int i=; i<=m; ++i)    scanf ("%d", &q[i]);

         sort (h+, h++n, cmp);

         int cnt = ;    int res = ;

         for (int i=, j=m; j>=; --j)

         {

             for (; i<=n; ++i)

             {

                 if (h[i].val <= q[j])    break;

                 int pos = h[i].id;

                 vis[h[i].id] = ;

                 if (!vis[pos-] && !vis[pos+])    res++;

                 if (vis[pos-] && vis[pos+])    res--;

             }

             ans[j] = res;

         }

         printf ("Case #%d: ", ++cas);

         for (int i=; i<=m; ++i)    printf ("%d%c", ans[i], (i==m) ? '\n' : ' ');

     }

     return ;

 }

 /*

 Case #1: 1 1 2

 Case #2: 1 2 1 1 0

 */