解題區/解題區 - UVa

UVa 12855 - Black and white stones

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

目標將所有的黑色 (B) 搬到最左邊。隨意位置交換兩元素成本為 A，相鄰交換成本為 B。

求花費最少為何？

Sample Input

1
2
3
4
5
6
2 1
BWWB
5 3
WBWWBWBWBWBBBWWBBB
1000000 0
W

Sample Output

1
2
3
2
27
0

Solution

很簡單地發現，隨意交換的時候，一定會去找相隔最遠的 W 和 B 進行交換。而相鄰交換的成本是推過去減少的逆序對數乘上 B。因此只要考慮 A 是否小於 B 乘上最遠兩端交換 減少的逆序對數 ，就一直使用隨意交換。直到不行，則全採用相鄰交換。

然而，我卡在 減少的逆序對數 ，不小心寫成總逆序對數。因此一直掛 WA。

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
52
53
54
55
56
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    long long A, B;
    char s[8192];
    while (scanf("%lld %lld", &A, &B) == 2) {
        scanf("%s", s);
        B = A - B;
        int n = strlen(s);
        long long ret = 0;	
        long long inv = 0, w = 0, b = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'W')	w++;
            else				inv += w;
        }
        int fw = 0, fb = n;
        for (int i = 0; i < n; i++)
            if (s[i] == 'W')	fw = i, i = n;
        for (int i = n-1; i >= 0; i--)
            if (s[i] == 'B')	fb = i, i = -1;
        w = b = 0;
        for (int i = fw; i <= fb; i++)
            if (s[i] == 'W')	w++;
            else				b++;
        while (inv) {
            if ((w + b - 1) * B <= A) {
                ret += inv * B;
                inv = 0;
            } else {
                ret += A;
//				swap(s[fw], s[fb]);
                inv -= w + b - 1, w--, b--;
                fw++, fb--;
                while (fw <= fb && s[fw] != 'W')	fw++, b--;
                while (fb >= fw && s[fb] != 'B')	fb--, w--;
            }
        }
        printf("%lld\n", ret);
    } 
    return 0;
}
/*
2 1
BWWB
5 3
WBWWBWBWBWBBBWWBBB
1000000 0
W
5 5
BWBWBWBWBBWBWBWB
24 22
BWWWWBWWWWWBWWBBBBWBWBWWBWBWW
*/