题目:计算机软件能力认证考试系统
特别注意评测用例规模与约定!
70 的测试数据满足 n≤100、r≤10。
全部的测试数据满足 0<n≤600、0<r≤100 且 2≤t<L≤256。
思路:
刚开始直接用四层for循环遍历,暴力求解,只得了70分,运行时间超时,需要对代码的循环进行优化。
通过分析可以知道,矩阵中同一行元素邻域的纵向范围是一样的,变化的是横向范围,并且同一行相邻的两个元素的邻域范围重合度非常高,所以我们可以用同一行的前一个元素的邻域来避免重复计算。
在同一行中,元素邻域的范围经历扩张、大小不变位置平移以及收缩这三个阶段。(j是元素在某一行的位置,r是邻域的范围)
j-r<=0时,(相比于前一个元素)邻域扩张,这时需要考虑j+r是否超过了矩阵的边界:
若j+r超过了矩阵边界,邻域范围不变(特殊情况);否则,邻域将扩张。
j-r>0时,(相比于前一个元素)邻域有平移和收缩两种情况:
当j+r<=n-1时,邻域大小保持不变位置向右平移;当j+r>n-1时,邻域开始收缩。
代码1:暴力遍历(70分)
#include<iostream>
using namespace std;
int twoArray[600][600];
int main(){
// n是矩阵的边长,L是最大灰度值,r指明附近元素的具体范围,t是阈值
int n,L,r,t;
cin>>n>>L>>r>>t;
// count计数暗区域总数
int count=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>twoArray[i][j];
}
}
for(int i = 0;i<n;i++){
for(int j=0;j<n;j++){
double temp = 0; // 记录某元素附近所有元素的像素和
int num = 0; // 记录某元素附近所有元素个数
// k1到k4表示某元素附近元素的边界
int k1=0,k2=0,k3=0,k4=0;
if(j-r<0){ k1=0; } // 横向左
else if(j-r>=0){ k1=j-r; }
if(j+r>=n){ k2=n-1; } // 横向右
else if(j+r<n){ k2 = j+r; }
if(i-r<0){ k3=0; } // 纵向上
else if(i-r>=0){ k3=i-r; }
if(i+r>=n){ k4=n-1; } // 纵向下
else if(i+r<n){ k4=i+r; }
for(int m=k3;m<=k4;m++){
for(int n=k1;n<=k2;n++){
temp+=twoArray[m][n];
num++;
}
}
if((double)(temp/num) <= t){
count++;
}
}
}
cout<<count;
}
代码2:优化后(100分)
#include<iostream>
using namespace std;
int twoArray[600][600];
int main(){
int n,L,r,t;
cin>>n>>L>>r>>t;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>twoArray[i][j];
}
}
int count = 0;
// 计算均值
for(int i=0;i<n;i++){
// 先算出每行第一个元素的邻域值之和
int start_y=i-r>0?i-r:0;
int bound_y=i+r>n-1?n-1:i+r;
int bound_x=0+r>n-1?n-1:r;
double sum = 0;
int num = 0;
for(int j=start_y;j<=bound_y;j++){
for(int k=0;k<=bound_x;k++){
sum+=twoArray[j][k];
num++;
}
}
if((sum/num)<=t){
count++;
}
// 同一行元素的 start_y bound_y都是一样的,不一样的是横向的边界
for(int j=1;j<n;j++){
if(j-r<=0){
if(j+r<=n-1){
// 邻域范围在扩张
for(int k=start_y;k<=bound_y;k++){
sum+=twoArray[k][j+r];
num++;
}
}
}
else if(j-r>0){
if(j+r<=n-1){
// 邻域范围不变
for(int k=start_y;k<=bound_y;k++){
sum=sum+twoArray[k][j+r]-twoArray[k][j-r-1];
// num值不变
}
}
else{
// 邻域范围在收缩
for(int k=start_y;k<=bound_y;k++){
sum-=twoArray[k][j-r-1];
num--;
}
}
}
if((sum/num)<=t){
count++;
}
}
}
cout<<count;
}