Responsive image

问题 1177 --每行选一个

1177: 每行选一个

时间限制: 3 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

新学期伊始,ACM老师又在为如何给学生分配课程设计题目而犯愁,ACM老师老共有 N 名学生和 M 个可选的题目,根据这些学生平时的表现,ACM老师精确计算出了每名学生完成各个课程设计题目所需的时间,现ACM老师要给每名学生分配一个题目,使得最快完成课程设计同学所需的时间与最慢完成课程设计同学所需的时间的差最小。

输入描述

第一行给出正整数 T(1<=T<=10 ),表示共有 T 组测试数据,每组测试数据,首先给出两个正整数 N(0<N<=200),M( 0<M<=10),接下来给出 N 行,每行包含 M 个正整数,第 i 行的第 j 个正整数代表第 i 名同学完成第 j 个课程设计所需的时间 p ( 0<=p<=1000 )。

输出描述

对于每组测试数据,单行输出最小差值。

样例输入

3
2 2
1 1
1 1
3 4
2 4 5 8
6 2 1 9
4 6 8 5
2 3
1 2 3
10 12 10

样例输出

0
1
7

提示

题意就是让你在N*M的矩阵中挑出N个数，这N个数两两不同行（也就是每行选一个），且保证挑选出来的N个数中最大值和最小值之差最小。

来源

黄庆浩 

[提交][状态]
ACM算法攻关部