NYOJ练习题 下三角矩形 (模拟)
下三角矩阵时间限制:1000 ms | 内存限制:65535 KB
描述
给定一个由0和1组成的矩阵。只允许交换相邻的两行,要把矩阵转化成下三角矩阵(主对角线上方的元素都是0),最少需要交换几次?输入的矩阵保证总能转化成下三角矩阵。
输入
多组测试数据。
每组测试数据第一行为一个整数n(1 <= n < 1000),表示矩阵的大小为n*n;
接下来n行,每行有n个数表示这个矩阵。
输出
输出最小需要交换的次数,单独占一行。
样例输入
3
0 0 1
1 0 0
0 1 0
样例输出
2
分析可知:构成下三角矩阵实际上只与每行的最后一个非零位置有关。
先找出矩阵中每行的最后一个非零位置,然后根据最后一个非零位置将其移动到对应的位置即可,从第一行开始,每一次移动符合条件的最邻近的一行,之后此行将不再考虑,记录移动的次数即为最少的次数。
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int a[1005][1005]; //记录矩阵 int c[1005]; // 记录每一行最后一个非零的数所在位置 int main() { int n, i, j, k; while(~scanf("%d",&n)) { memset(c,0,sizeof(c)); for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { scanf("%d",&a[i][j]); if(a[i][j]) c[i] = j; //记录每一行最后一个非零的数所在位置 } } int ans = 0; //交换次数 for(i = 1; i <= n; i++) //从第一行开始找 { int pos = 0; for(j = i; j <= n; j++) //找与当前行最邻近的满足条件的行 { if(c[j] <= i) { pos = j; break; } } for(k = pos; k > i; k--) { swap(c[k],c[k-1]); ans++; } } printf("%d\n",ans); } return 0; }
补充:软件开发 , C++ ,