Algoogle

Algorithm for Programming Contest

ACM-ICPC Tokyo Regional 2014 A Bit String Reordering

Category: ICPC Tag: greedy

Automotive Navigation

問題概要


目標のビット列が与えられる. 今現在のビット列から隣同士を最小何回swapさせれば目標のビット列になるか. ただし元の列は0と1どちらかわからない(どちらかが何個続くという情報の列が与えられる). 元の列から目標の列は生成可能.

解法


左から詰めていけばよい.
現在のビットが目標と違ったらそれより先にあるもののうち最初に現れる目標の値の場所とswapし, その距離をコストとする.
その間に目標と違う値が敷き詰められているので目標の値を順にswapさせてきても影響がないためそれで問題ない.

コード


(A.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

int n, m, b[16], p[16], cnt[2], cnt2[2];

int calc(int s)
{
        int r[16] = {}, cur = 0;
        for (int i = 0; i < m; i++) {
                for (int j = 0; j < p[i]; j++)
                        r[cur++] = s;
                s ^= 1;
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
                if(r[i] == b[i]) continue;
                for (int j = i+1; j < n; j++) {
                        if(r[j] == b[i]) {
                                ret += j-i;
                                r[j] = r[i];
                                break;
                        }
                }
        }
        return ret;
}

int solve()
{
        for (int i = 0; i < n; i++) cnt[b[i]]++;
        for (int i = 0; i < m; i++) cnt2[i%2] += p[i];
        if(cnt[0] == cnt[1]) return min(calc(0), calc(1));
        if(cnt[0] == cnt2[0]) return calc(0);
        return calc(1);
}

void input()
{
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> b[i];
        for (int i = 0; i < m; i++) cin >> p[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments