【Bit String Reordering UVALive - 6832 】【模拟】

题意分析

题目讲的主要是给你一个01串，然后给你要变成的01串格式，问你要转换成这一格式最少需要移动的步数。

题目不难，但当时并没有AC，3个小时的个人赛1道没AC，归根到底是没有逼自己去想，又想的太多，还没敢去想，还是太菜，最后把自己整崩溃了，过后看完别人代码发现此题并不难，模拟即可，现附具体分析如下。

分析：既然已经给了你具体要求的01串，那么这样的01串只能有两个。只需将转化成这两种01串所需要的步数取最小即可。现附AC代码如下。

AC代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

void Swap(int& a, int &b)

{

    int t = b;

    b = a;

    a = t;

}

int getSum(int a[], int len)

{

    int sum = 0;

    for(int i = 0; i < len; i++)

        sum += a[i];

    return sum;

}

const int maxn = 20, INF = 0x3f3f3f3f;

int N, M;

int b[maxn], p, bb[maxn];

int cal()

{

    if(getSum(b, N) != getSum(bb, N))       //若连和都不同，再交换相邻元素又有何用

        return INF;

    int cnt = 0, temp[maxn];

    memcpy(temp, b, sizeof(b));         //这里要注意，将你要变换的串存储在一个临时的串中，这样在得到交换次数的同时又不会改变原串

    for(int i = 0; i < N; i++)

    {

        if(bb[i] == temp[i]) continue;

        for(int j = i + 1; j < N; j++)

        {

            if(bb[i] == temp[j])        //找到相等的后，依次交换相邻的元素，直到它到达指定位置

            {

                while(i < j)

                {

                    Swap(temp[j-1], temp[j]);

                    --j;

                    cnt++;

                }

                break;

            }

        }

    }

    return cnt;

}

int main()

{

    // freopen("input.txt", "r", stdin);

    // freopen("output.txt", "w", stdout);

    while(scanf("%d%d", &N, &M)  != EOF)

    {

        memset(b, 0, sizeof(b));

        for(int i = 0; i < N; i++)

            scanf("%d", &b[i]);

        int idx = 0, value = 1;

        while(M--)

        {

            scanf("%d", &p);

            while(p--)

                bb[idx++] = value;

            value ^= 1;     //这里用异或的原因是利用它不进位的加法的特性

        }

        int minn = INF;

        minn = min(minn, cal());

        for(int i = 0; i < N; i++)

            bb[i] ^= 1;     //在看另一种符合要求的01串

        minn = min(minn, cal());

        printf("%d\n", minn);

    }

}

巴特西

【Bit String Reordering UVALive - 6832 】【模拟】

题意分析

AC代码

最新文章

热门文章