涂条纹
题目描述
算法解析
由于要涂颜色，首先要进行数据预处理。记录每行各颜色的修改次数，定义数组w[]、b[]、r[]表示白、蓝和红在第i行需要修改多少次才能变成该颜色。
紧接着就要用到暴力枚举了，由于题目要求3种颜色都得有，因此白色最多只能覆盖到n-2行，而红色最早得从第2行开始。有了基本思路，就可以设计代码。
（1）首先预处理每行各颜色的修改次数，其次使用双重循环枚举颜色的边界，内部for循环统计根据i、j设置的边界需要改颜色的格子数，最终取最小值。
【参考代码】
#include
#include
using namespace std;
string s[55];
int w[55],b[55],r[55];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){ cin>>s[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){ //注意字符串是从0开始的
if(s[i][j]!='W')w[i]++;
if(s[i][j]!='B')b[i]++;
if(s[i][j]!='R')r[i]++;
}
}
int ans=250000; //先假设一个较大值作为ans
for(int i=1;i<n-1;i++){ //i为白色最后一行
for(int j=i+2;j<=n;j++){ //j为红色的第一行
int sum=0;
for(int x=1;x<=i;x++) sum+=w[x]; //1~i行变为白色
for(int y=i+1;y<j;y++) sum+=b[y]; //i+1~j-1行变为蓝色
for(int z=j;z<=n;z++) sum+=r[z]; //j~n行变为红色
ans=min(sum,ans); //取较小值
}
}
cout<<ans;
return 0;
} （2）在上述代码中，程序的时间复杂度为O(n^3)（其中三重for循环的最内侧三个循环加一块就是n行数据的处理），能不能稍微降低一下时间呢？
我们发现，三重循环的最内侧循环，实际在计算对应数组的区间和，例如“for(int x=1;x<=i;x++) sum+=w[x];”这段代码的本质是求w[]数组在区间1~i的和。
由此，我们可以想到使用前缀和算法来优化这部分代码的计算。用前缀和代替这部分的for循环后，程序的时间复杂度就降到了O(n*m+n^2)。
关于前缀和算法的介绍，可以阅读往期的文章——C++信奥之径，锻炼思维，扎实算法——排序算法（1）
【参考代码】
#include
#include
using namespace std;
string s[55];
int w[55],b[55],r[55];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){ cin>>s[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
if(s[i][j]!='W')w[i]++;
if(s[i][j]!='B')b[i]++;
if(s[i][j]!='R')r[i]++;
}
}
for(int i=1;i<=n;i++){ //前缀和算法处理数组
w[i]+=w[i-1];
b[i]+=b[i-1];
r[i]+=r[i-1];
}
int ans=250000;
for(int i=1;i<n-1;i++){
for(int j=i+2;j<=n;j++){
int tmp=w[i]+b[j-1]-b[i]+r[n]-r[j-1];
//w[i]对应1~i行的白色修改数之和
//b[j-1]-b[i]对应i+1~j-1行蓝色修改数之和
//r[n]-r[j-1]对应j~n行红色修改数之和
ans=min(ans,tmp);
}
}
cout<<ans;
return 0;
} 运行结果