首页 > ACM题库 > 九度OJ > 九度-1191-矩阵最大值[解题代码]
2013
12-13

九度-1191-矩阵最大值[解题代码]

题目来源:2007年华中科技大学计算机研究生机试真题

题目描述:

编写一个程序输入一个mXn的矩阵存储并输出,并且求出每行的最大值和每行的总和。
要求把每行总和放入每行最大值的位置,如果有多个最大值,取下标值最小的那一个作为最大值。
最后将结果矩阵输出。

输入:

输入的第一行包括两个整数m和n(1<=m,n<=100),分别代表矩阵的行和列的维数。
接下来的m行每行有n个数,代表矩阵的元素。

输出:

可能有多组测试数据,对于每组数据,输出按题目要求执行后的矩阵。

样例输入:
3 3
1 1 1
1 1 1
1 1 1
3 3
3 2 3
2 3 2
3 2 3
样例输出:
3 1 1
3 1 1
3 1 1
8 2 3
2 7 2
8 2 3

cpp 代码如下:
#include <cstdlib>
#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    int m ;
    int n ;
    while(scanf("%d %d",&m,&n) != EOF){
          int ** arr = new int*[m]; 
          for(int i =0; i<m; i++){
          arr[i] = new int[n];
          } 
          for(int i=0; i<m; i++){
				int maxIndex = 0;
				int sum = 0;
				for(int j=0; j<n; j++){
                        int temp;
					scanf("%d",&temp);
					arr[i][j] = temp;
					if(arr[i][maxIndex] < temp) 
						maxIndex = j;  //得到最大值的下标
					sum += temp; //计算没行的值
				}
				arr[i][maxIndex] = sum; //替换最大值 为 和
			}
            
            for(int i=0; i<m; i++){
                    for(int j=0; j<n; j++){
                            if(j != n-1)
                                 printf("%d ",arr[i][j]);
                             else
                                 printf("%d\n",arr[i][j]);        
                    }  
                     
            }       
    }

    return 0;
}

/**************************************************************
	Problem: 1191
	User: coder
	Language: C++
	Result: Accepted
	Time:80 ms
	Memory:2172 kb
****************************************************************/


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮