1578: 自习教室
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 258 Solved: 24
[Submit][Status][Web Board]Description
快期末了，小明要开始预习课本了，作为一名爱玩的学渣，他需要找一个相对最安静的位置来学习，然而图书馆还是会有一些人不安分的发出噪音，现在给出一张n*m的矩阵来表示图书馆的状态。如果这个点是0则表示这个对应的位置为空，如果不是0则表示这里有个会发出噪音系数为a的人存在，噪音是会随着距离的增加而降低的，降低的幅度等于距离，两个点的距离用|x1-x2|+|y1-y2|表示
Input
多组测试数据
第一行包含两个数字n和m和k(0<n,m<100,0<=k<=n*m)表示图书馆的长和宽
接下来k行，每行三个数字i,j,s(0<=i<n,0<=j<m,0<s<10)表示噪音源的坐标以及噪音系数
Output
输出最安静的位置i，j（表示i行j列）以及受到的噪音指数是多少，如果有多个答案输出i最小的，若i一样输出j最小的
Sample Input
3 3 1
1 1 3
Sample Output
0 0 1
【分析】直接搜的话，是会超时的，因为k是m*n，那就是100*100*10000，超了。之后，改了一下，但是还是会超时，因为每次循环执行一下abs()函数是很费时间的。那么，就优化val[]数组的赋值吧。
【代码】
#include<bits/stdc++.h>
using namespace std;
int val[105][105];//每个位置的值的总和
int main()
{int n,m,k;while(~scanf("%d%d%d",&n,&m,&k)){memset(val,0,sizeof(val));while(k--){int x,y,s;scanf("%d%d%d",&x,&y,&s);val[x][y]+=s;for(int i=1;i<s;i++){if(x+i<n)val[x+i][y]+=s-i;if(y+i<m)val[x][y+i]+=s-i;if(x-i>=0)val[x-i][y]+=s-i;if(y-i>=0)val[x][y-i]+=s-i;}for(int i=1;i<s;i++){for(int j=1;j<s;j++){if(i+j<s){if(x-i>=0 && y-j>=0)val[x-i][y-j]+=s-i-j;if(x+i<n && y+j<m)val[x+i][y+j]+=s-i-j;if(x-i>=0 && y+j<m)val[x-i][y+j]+=s-i-j;if(x+i<n && y-j>=0)val[x+i][y-j]+=s-i-j;}}}}int minn=0x3f3f3f3f;int ansi=0,ansj=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(val[i][j]<minn){minn=val[i][j];ansi=i,ansj=j;}}}printf("%d %d %d\n",ansi,ansj,minn);}return 0;
}