[USACO07MAR] Face The Right Way G

题目描述

$N$ 头牛排成一列 $1 \le N \le 5000$。每头牛或者向前或者向后。为了让所有牛都面向前方，农夫每次可以将 $K$ 头连续的牛转向 $1 \le K \le N$，求使操作次数最小的相应 $K$ 和最小的操作次数 $M$。$F$ 为朝前，$B$ 为朝后。

请在一行输出两个数字 $K$ 和 $M$，用空格分开。

输入格式

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

样例输入 #1

7
B
B
F
B
F
B
B

样例输出 #1

3 3

题目分析

阅读题面可知，题目要求两个东西：

1. 最小反转的连续区间长度K
2. 使所有奶牛朝向前方的最小操作次数 m

且K是建立在最小操作次数m的基础上，若存在多个最小操作次数的反转长度，取其中的最小值。概括后是一个满足条件的最值问题。可以考虑使用枚举法。

for(int i=1;i<=n;i++){
    int cnt=count(i);//求出以i为反转长度时的最小操作次数
    if(cnt<m){//打擂台更新最值
        m=cnt;
        k=i;
    }
}

在此框架基础上，可发现，目前的问题是解决在已知反转的连续区间长度后，如何求出最少的操作次数？

只有正、反两个方向，反转奇数次能变成其他方向，反转偶数次相当于没有变化。我们从前往后进行反转，若当前位置是正向，则不用反转它；如果是反向，则将这个位置开始的连续k个元素进行反转,从而保证遍历过的元素都是正向的。

//核心操作
for(int i=1;i<=n;i++){
    if(a[i]==0 && i+k-1<=n){
        cnt++;//更新操作次数
        for(int j=i;j<=i+k-1;j++){
            a[i]^=1;//反转
        }
    }
}

当前操作复杂度为 $O(nk)$,那么整体复杂度就是$O(n^3)$ 的，会存在超时的情况。

那么如何进行优化呢？

耗时较长的部分在于确定k之后求最小的操作次数这块，每次修改长度为k的区间时，我们都是暴力循环进行处理的。那么是否可以加速区间修改这块操作呢？

回到之前的分析，两个状态进行反转，反转偶数次就是没变化，反转奇数次就变成另一个状态了。那么我们可以就将状态的直接修改，更改为记录反转的次数，将原始状态与反转次数进行当前状态的确定。从而将区间每个元素的反转更改为对应区间内反转次数+1,也就是连续区间内统一增减一个数，这是非常典型的差分的应用。我们可以用差分的思想优化这块。

for(int i=1;i<=n;i++){
    s[i]=s[i-1]+b[i];//求当前的反转次数
    if((s[i]+a[i])%2==0 && i+k<=n){
        cnt++;//更新修改次数
        //[i,i+k-1] 差分思路修改
        b[i]++;
        b[i+k]--;
    }
    s[i]=s[i-1]+b[i];
    //....
}

这样的化求最小操作次数这部分的时间复杂度就降为了 $O(n)$,整体复杂度就是 $O(n^2)$ ，可以满足数据的要求。

代码实现

// Problem: Face The Right Way G
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 5005;
int a[N],b[N],s[N],n;
int count(int k){
    for(int i=1;i<=n;i++){
        b[i]=0;//初始化差分数组
    }
    int cnt=0;//最小操作次数
    bool f=0;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+b[i];
        //1+奇数次 or 0+偶数次 并执行长度足够k个时 可以进行反转
        if((s[i]+a[i])%2==0 && i+k-1<=n){
            //a[i]~a[i+k-1]
            cnt++;
            b[i]++;
            b[i+k]--;
        }
        s[i]=s[i-1]+b[i];
        if((s[i]+a[i])%2==0){//长度不够反转，且存在无法反转为正向的
            f=1;
            break;
        }
    }
    if(f) return 1e9;
    else return cnt;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  char c;
  cin>>n;
  for(int i=1;i<=n;i++){
      cin>>c;
      a[i]=(c=='B')?0:1;
  }
  int minl=1e9,minm=1e9;
  for(int i=1;i<=n;i++){//枚举所有可能的反转长度
    int cnt=count(i);
    if(cnt<minm){
        minl=i;
        minm=cnt;
    }
  }
  cout<<minl<<" "<<minm;
  return 0;
}