[ACM]The Best Seat in ACM Contest

本文主要是介绍[ACM]The Best Seat in ACM Contest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入

输出

示例输入

13 41 5 3 46 3 3 44 3 2 1

示例输出

Case 1: 7 1 1

解题思路：

使用两数组a,b，a用来保存原数据，b用来存放相应位置每个原数据计算后的数据，即保存每个原数据的状态变量。对数据进行分情况。1，四个角的数据，需要进行2次运算。2，最外面四条边上，去掉角剩下的中间数据，需要进行三次运算。3，去掉外面的一圈数据剩下的原数据，需要进行四次运算，上下左右。一开始在算法上出了错误，不是不对，而是特别麻烦，折腾的头晕眼花，每次计算都用if 怎么样，然后else 怎么样，后来慢慢发现，其实不用判断所要进行计算的原数据的相邻数据是否比它大还是小，直接用相邻数据减去原数据即可，大大减少了代码量，而且效率高。

代码：

#include <iostream>
using namespace std;
int a[21][21];//用来放原数据
int b[21][21];//用来放计算后的数据
int main()
{
int T,t;
cin>>T;
for(t=1;t<=T;t++)
{
int i,j,i1,j1;//数组i行，j列
cin>>i>>j;
for(i1=0;i1<i;i1++)
for(j1=0;j1<j;j1++)
{
cin>>a[i1][j1];
b[i1][j1]=0;//数组b初值全部为0
}
b[0][0]+=-2;//考虑数组的左上角数据,因为有两侧没有相邻数据，所以减去2分
b[0][j-1]+=-2;//右上角
b[i-1][0]+=-2;//左下角
b[i-1][j-1]+=-2;//右下角
b[0][0]+=a[0][1]-a[0][0];//下面分别对四个角的数据计算，每个数据计算两次
b[0][0]+=a[1][0]-a[0][0];//计算的时候不需比较相邻数据，直接用相邻数据减去本数据即可满足题目要求，b数组保留每次计算的结果
b[i-1][0]+=a[i-2][0]-a[i-1][0];
b[i-1][0]+=a[i-1][1]-a[i-1][0];
b[0][j-1]+=a[0][j-2]-a[0][j-1];
b[0][j-1]+=a[1][j-1]-a[0][j-1];
b[i-1][j-1]+=a[i-2][j-1]-a[i-1][j-1];
b[i-1][j-1]+=a[i-1][j-2]-a[i-1][j-1];
for(i1=1;i1<=i-2;i1++)//考虑数组最左边中间的数据，每个数据需要计算三次
{
b[i1][0]+=-1;//一侧没有相邻数据，减去1分
b[i1][0]+=a[i1][1]-a[i1][0];//右减左
b[i1][0]+=a[i1-1][0]-a[i1][0];//上减下
b[i1][0]+=a[i1+1][0]-a[i1][0];//下减上
}
for(j1=1;j1<=j-2;j1++)//最上边中间的数据
{
b[0][j1]+=-1;
b[0][j1]+=(a[1][j1]-a[0][j1]);
b[0][j1]+=(a[0][j1-1]-a[0][j1]);
b[0][j1]+=(a[0][j1+1]-a[0][j1]);
}
for(j1=1;j1<=j-2;j1++)//最下边中间的数据
{
b[i-1][j1]+=-1;
b[i-1][j1]+=a[i-2][j1]-a[i-1][j1];
b[i-1][j1]+=a[i-1][j1-1]-a[i-1][j1];
b[i-1][j1]+=a[i-1][j1+1]-a[i-1][j1];
}
for(i1=1;i1<=i-2;i1++)//最右边中间的数据
{
b[i1][j-1]+=-1;
b[i1][j-1]+=a[i1][j-2]-a[i1][j-1];
b[i1][j-1]+=a[i1-1][j-1]-a[i1][j-1];
b[i1][j-1]+=a[i1+1][j-1]-a[i1][j-1];
}//到这里已经把a数组里的最外面一圈的数据处理完毕，把处理结果都放到相应位置的b数组中了
for(i1=1;i1<=i-2;i1++)//处理内部数据
for(j1=1;j1<=j-2;j1++)
{
b[i1][j1]+=a[i1-1][j1]-a[i1][j1];//每个数组都需要计算四次
b[i1][j1]+=a[i1+1][j1]-a[i1][j1];
b[i1][j1]+=a[i1][j1-1]-a[i1][j1];
b[i1][j1]+=a[i1][j1+1]-a[i1][j1];
}//到这里a数组里的全部数据计算完毕
int m,n,max,x,y;//x,y用来标记b数组中最大数的 行数 和 列数,max用来求b数组中的最大值
max=b[0][0];
for(m=0;m<=i-1;m++)
for(n=0;n<=j-1;n++)//遍历b数组
{
if(max<=b[m][n])
{
max=b[m][n];
x=m;
y=n;
}
}
cout<<"Case "<<t<<": "<<max<<" "<<x+1<<" "<<y+1<<endl;
}
return 0;
}

运行截图：

这篇关于[ACM]The Best Seat in ACM Contest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！