NYOJ练习题 下三角矩形 （模拟）
下三角矩阵时间限制：1000 ms | 内存限制：65535 KB- 描述
给定一个由0和1组成的矩阵。只允许交换相邻的两行,要把矩阵转化成下三角矩阵（主对角线上方的元素都是0），最少需要交换几次？输入的矩阵保证总能转化成下三角矩阵。
- 输入
- 多组测试数据。
每组测试数据第一行为一个整数n（1 <= n < 1000），表示矩阵的大小为n*n；
接下来n行，每行有n个数表示这个矩阵。 - 输出
- 输出最小需要交换的次数，单独占一行。
- 样例输入
30 0 11 0 00 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;}
给定一个由0和1组成的矩阵。只允许交换相邻的两行,要把矩阵转化成下三角矩阵（主对角线上方的元素都是0），最少需要交换几次？输入的矩阵保证总能转化成下三角矩阵。
- 输入
- 多组测试数据。
每组测试数据第一行为一个整数n（1 <= n < 1000），表示矩阵的大小为n*n；
接下来n行，每行有n个数表示这个矩阵。 - 输出
- 输出最小需要交换的次数，单独占一行。
- 样例输入
30 0 11 0 00 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;}