POJ-3276-Face The Right Way

题目描述：

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same location as before, but ends up facing the opposite direction. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

输入：

Line 1: A single integer: N
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

输出：

Line 1: Two space-separated integers: K and M

输入示例：

1
2
3
4
5
6
7
8
7
B
B
F
B
F
B
B

输出示例：

1
3 3

暗示：

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)

题目大意：

有N头牛，牛要么朝前要么朝后，一次操作只可以翻转区间内的所有牛，问最小的翻转次数和相应最小的翻转区间。

思路：

首先，这是一个开关问题，一般性的开关问题具有两个性质：

  • 切换状态的顺序对结果不影响。

  • 一个开关按偶数次等于不按。

解决这个问题光有这两性质还不够，我们先求如果知道了区间长度K，如何求最小翻转次数M。

我们先选择考虑最左端的牛，如果该牛朝向前，则不需要翻转，所以范围可以缩减1，如果该牛朝向后，则必须翻转该区间了。我们贪心的翻转遇到的第一个朝向后的牛，就可以求出来最少的翻转次数了。

这样我们枚举K,并且每个K都需要检查N-K+1个区间，每个区间的检查又需要O(N)的时间，所以总的时间为O(N^3)。达不到题目要求的时限。

优化：

我们的目标是将所有的朝向后面的牛翻转，所以牛朝向决定了该区间是否发生翻转。我们将关注点移动到每个具体的牛与之前已经翻转的次数的关系上。

对于每个牛，与所在区间的已翻转次数有下列四种情况：

  • 当前牛朝向前，已经翻转了偶数次。

  • 当前牛朝向后，已经翻转了奇数次。

  • 当前牛朝向前，已经翻转了奇数次。

  • 房钱牛朝向后，已经翻转了偶数次。

我们结合前面开关问题的第二条性质发现：前两种情况不需要进行任何操作。后两种情况则需要进行一次翻转。所以结论就是：

如果朝向前为0，朝向后为1，则

当前牛的朝向 + 之前已经翻转的次数 = 奇数

的时候则说明该翻转了。

这样，可以在常数时间内知道每个区间的翻转次数。优化到了O(N^2)，能在时限内解决了。

Solution：

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
57
58
59
60
61
62
/*
 * @Date: 2019-09-17 17:05:23
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-17 18:13:33
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int N,K,M;
const int MAXN = 1e5+10;
int dir[MAXN];
int f[MAXN];

int cal(int k){
    // 表示区间[i, i+k-1] 是否翻转
    memset(f,0,sizeof(f));
    int sum = 0;//区间内翻转的次数
    int res = 0;
    for(int i = 0; i + k-1 < N; i++){
        //当牛的朝向与之前已翻转的次数。
        if((dir[i] + sum) % 2 != 0){
            res++;
            f[i] = 1;
        }
        //更新翻转次数
        sum += f[i];
        //固定区间
        if(i - k + 1 >= 0){
            sum -= f[i-k+1];
        }
    }
    //由于前n-k+1个 已经翻转到正面了，只有当后面的牛都不用翻转才合法。
    for(int i = N-k+1; i < N; i++){
        if((dir[i] + sum) % 2 != 0) return -1;
        //固定区间
        if(i - k + 1 >= 0) sum -= f[i-k+1];
    }
    return res;
}

int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    K = 1, M = N;
    char c[3];
    for(int i = 0; i < N; i++){
        scanf("%s",c);
        if(c[0] == 'B') dir[i] = 1;
    }   
    //枚举K
    for(int k = 1; k <= N; k++){
        int m = cal(k);
        if(m >= 0 && m < M){
            M = m;
            K = k;
        }
    }
    printf("%d %d",K,M);
}