贪心 UVALive 6832 Bit String Reordering

题目传送门

 /*

     贪心：按照0或1开头，若不符合，选择后面最近的进行交换。然后选取最少的交换次数

 */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <string>

 #include <cmath>

 #include <vector>

 #include <map>

 #include <queue>

 using namespace std;

 const int MAXN =  + ;

 const int INF = 0x3f3f3f3f;

 int a[MAXN], b[MAXN], c[MAXN];

 int main(void)        //UVALive 6832 Bit String Reordering

 {

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

     int n, m;

     while (scanf ("%d%d", &n, &m) == )

     {

         for (int i=; i<=n; ++i)    {scanf ("%d", &a[i]);    c[i] = a[i];}

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

         int cnt1 = , cnt2 = ;    int now = ;    int p = ;

         bool ok1 = true, ok2 = true;

         for (int i=; i<=m && ok1; ++i)

         {

             for (int j=; j<=b[i]; ++j)

             {

                 if (a[p+j] != now)

                 {

                     int k = p + j;

                     while (k <= n && a[k] != now)    k++;

                     if (k == n+ || a[k] != now)    {ok1 = false;    break;}

                     cnt1 += k - (p + j);

                     swap (a[k], a[p+j]);

                 }

             }

             p += b[i];    now =  - now;

         }

         now = ;    p = ;

         for (int i=; i<=m && ok2; ++i)

         {

             for (int j=; j<=b[i]; ++j)

             {

                 if (c[p+j] != now)

                 {

                     int k = p + j;

                     while (k <= n && c[k] != now)    k++;

                     if (k == n+ || c[k] != now)    {ok2 = false;    break;}

                     cnt2 += k - (p + j);

                     swap (c[p+j], c[k]);

                 }

             }

             p += b[i];    now =  - now;

         }

 //        printf ("%d %d\n", cnt1, cnt2);

         if (!ok1)    printf ("%d\n", cnt2);

         else if (!ok2)    printf ("%d\n", cnt1);

         else    printf ("%d\n", min (cnt1, cnt2));

     }

     return ;

 }