题目描述
time 5000ms memery 128MB 有道题目是这样的： 输入一个 n行 m列网格，找一个格子，使得它所在的行和列中所有格子的数之和最大。如果答 案不唯一，输出任意解即可。比如，在下面的例子中，最优解是(1,3)，即第一行和的三列的交 点（行从上到下编号为 1~n，列从左到右编号为 1~m），所有 7个数之和为 35。
快要比赛的时候，有一个裁判想到了这样一个算法： 首先找一行 r(1<=r<=n) 使得该行所有数之和最大，然后找一列 c(1<=c<=m) 使得该列 所有数之和最大，最后直接输出(r,c)。如果有多个满足条件的 r，输出最小的 r。对 于 c同样处理。
显然，这个算法是错的，但它竟然通过了大部分测试数据！你能找出那些让这个错误算法得到 正确结果的“弱”数据，以便裁判们改进这些数据吗？
输入
输入包含不超过 100组数据。每组数据第一行为两个整数 n, m (1<=n<=500, 1<=m<=500)，即行 数和列数。以下 n行每行包含 m个 1~100的整数。输入的总大小不超过 2MB。
输出
对于每组数据，如果错误算法能得到正确结果，输出”Weak”，否则输出”Strong”。
样例输入
4 4 5 5 5 5 1 1 5 1 1 1 5 1 1 1 5 1 5 4 2 5 1 1 1 1 9 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出
Case 1: Weak Case 2: Strong
思路
我是暴力写的这道题，找出这个错误的算法的最大值取得的位置，再暴力找到正确的最大值的位置，都是大于的情况下更新，因为多个最大值的位置取行数小的。
代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <string>
#define mem(a) memset(a,0,sizeof(a))
#define mem2(a) memset(a,-1,sizeof(a))
#define mod 1000000007
#define mx 100005
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
freopen(
"1.txt",
"r",stdin);
#endif
ios_base::sync_with_stdio(
false);
cin.tie(
0);
int n,m,t;
int cas=
0;
long long int a[
510][
510];
int x,y,p,q;
int weak,strong;
while(
cin>>m>>n)
{
mem(a);
for(
int i=
1; i<=m; ++i)
{
t=
0;
for(
int j=
1; j<=n; ++j)
cin>>a[i][j],t+=a[i][j];
a[i][
0]=t;
}
for(
int i=
1; i<=n; ++i)
{
t=
0;
for(
int j=
1; j<=m; ++j)
t+=a[j][i];
a[
0][i]=t;
}
weak=-
1;
for(
int i=
1; i<=m; ++i)
if(weak<a[i][
0])
weak=a[i][
0],t=i;
x=t;
strong=-
1;
for(
int j=
1; j<=n; ++j)
if(strong<a[
0][j])
strong=a[
0][j],y=j;
weak+=strong;
weak-=a[x][y];
strong=-
1;
for(
int i=
1; i<=m; ++i)
for(
int j=
1; j<=n; ++j)
if(strong<a[i][j]*-
1+a[i][
0]+a[
0][j])
strong=a[i][j]*-
1+a[i][
0]+a[
0][j],p=i,q=j;
cout<<
"Case "<<++cas<<
": ";
if((x==p&&y==q)||(weak==strong))
cout<<
"Weak"<<endl;
else
cout<<
"Strong"<<endl;
}
return 0;
}
