[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
题目分析
阅读题面可知,题目要求两个东西:
- 最小反转的连续区间长度K
- 使所有奶牛朝向前方的最小操作次数 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;
}
10 条评论
《东京伤情故事特别篇》剧情片高清在线免费观看:https://www.jgz518.com/xingkong/95131.html
你的文章让我心情愉悦,每天都要来看一看。 http://www.55baobei.com/LwYhD8eNWC.html
你的才华让人瞩目,期待你的更多文章。 https://www.4006400989.com/qyvideo/12152.html
你的文章充满了智慧,让人敬佩。 https://www.4006400989.com/qyvideo/39174.html
你的文章内容非常专业,让人佩服。 https://www.yonboz.com/video/47119.html
你的文章让我心情愉悦,真是太棒了! https://www.yonboz.com/video/46451.html
你的文章让我感受到了艺术的魅力,谢谢! http://www.55baobei.com/LInx8xUK28.html
你的文章让我心情愉悦,真是太棒了! http://www.55baobei.com/fC8fnTV7Ev.html
你的才华让人瞩目,期待你的更多文章。 https://www.4006400989.com/qyvideo/70208.html
真棒!