暑假培训 2011-08-01
矩阵
给定一个N*N（N<=7）整数矩阵，定义对第i行的SHIFT操作（0<=i<N），是将第i行所有元素都右移一位，最右边的元素移到最左边。可以对任意行进行任意次SHIFT操作，使得所有列的元素的和的最大值最小。即MAX{Cj}最小，Cj是第j列元素的和。
输入：
有多个测试序列，每个测试序列第一行是一个整数N（1<=N<=7），表明矩阵的阶。后面n行每行n个整数，表示矩阵元素Aij（Aij<10000）。N=－1表示输入结束。
输出：
对任意行进行任意次SHIFT操作后， MAX{Cj}的最小值。
输入样例：
2
4 6
3 7
3
1 2 3
4 5 6
7 8 9
-1
输出样例：
11
15
解体代码：
#include <stdio.h>
#include <math.h>
#define N 7
int s[N][N]={0};
int main()
{
int i,j,k;
int m,n,t=32765;
int s1[N][N]={0},min[N];
printf("Please input juzheng number N:");
while(1){
do{ scanf("%d",&n);}while(n>N);
if(n<=0) return 0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&s[i][j]);
for(i=0;i<n*n;i++)
{
for(j=0;j<n;j++)
{
min[j]=0;
m=i;
for(k=0;k<n;k++){
min[j]+=s[k][(m/(int)pow(n,n-k-1)+j)%(n)];
m=m%(int)pow(n,n-k-1);
}
}
m=min[0];
for(j=0;j<n;j++)
{
if(min[j]>m)m=min[j];
}
if(m<t)t=m;
}
printf("%d\n",t);
}
return 0;
}