Face The Right Way POJ - 3276 题解

左手的ㄟ右手 2022-09-02 07:49 82阅读 0赞

## 题目链接 ##

> https://vjudge.net/problem/POJ-3276

开关问题  
K为反转块的大小，M为反转的次数  
（要求在最小的反转次数内，选择最小的反转块）

我们，首先从小到大遍历所有的单位块K，这样能保证在选择最小的反转次数M的同时，只会保留最小的块数K。

对于每一个可能的K值，  
如果能满足条件，则turn函数返回需要反转的次数，  
如果反转的次数比当前值要小，则更新最小的M，因为K是保证在最小M前提下的K，所以也要同时更新K值。

在turn函数的每一次处理中，以块为单位的思想进行推进，记录可以影响当前值的反转次数，偶数次反转为无效反转，奇数次反转为有效反转。

## AC代码 ##

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int N;
    const int MAX_N = 5000;
    bool dir[MAX_N];  // true -> 正向,false -> 反向
    bool f[MAX_N]; // true -> 反转  false -> 不反转
    
    int turn(int k)
    {
        
        memset(f, false, sizeof(f));
        int res = 0;
        int sum = 0;
        for (int i = 0; i + k <= 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];
            }
        }
        
        // 检查剩余部分是否还有没用旋转的牛
        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;
    }
    
    void solve()
    {
        
        int K = 1;
        int M = N; 
        for (int k  = 1; k <= N; ++k)
        {
        
            int m = turn(k); //如果能返回置换次数，如果不行，返回-1.
            if (-1 != m && m < M)
            {
        
                M = m;
                K = k;
            }
        }
        
        cout << K << ' ' << M << endl;
    }
    
    int main()
    {
        
        cin.tie(0);
        cout.tie(0);
        ios::sync_with_stdio(false);
        
        cin >> N;
        char ch;
        for (int i = 0; i < N; ++i)
        {
        
            cin.get();
            ch = cin.get();
            if (ch == 'F')
            {
        
                 dir[i] = true;
            }
            else
            {
        
                dir[i] = false;
            }
        }
        
        solve();
        return 0;
    }