问题遇到的现象和发生背景
来源码题集,求指教!
房间打归
难度:白眼
小码哥准备去打归一间房间,这个房间可以简单地看成由 n 行 n 列,共由nxn 个格子组成。每个格子的初始
状态要么是干净的,要么是脏的。小码哥打扫房间的方式非常奇怪:如果他打扫了一个脏格子,那么这个格子会变干净;反之亦然,如果他打扫了一个干净的格子,那么这个格子会变脏。他想从房间的 n 列格子中选择几列进行打扫,希望打扫完后完全干净的行数尽量多。注意,如果他选择了某一列进行打扫,则他需要打扫这一列包含的所有的格子;一行是完全干净的指这一行中所有格子都是干净的。
小码哥并不是很撞长数学,于是希望你帮他计算一下,如果他使用合理的打归策略,完全干净的行数最多可以有多少行?
格式
输入格式:第一行输入一个整数 n (1< n <200),表示房间的大小。
然后接下来输入 n 行,第i行包含个长度为 n 的01字符串,表示房间第 i 行格子的初始状态,第 j 个字符为1表示第 i 行第 j 列的格子是干净的,为0表示是胜的。
输出格式:输出一个整数,表示最大可能的完全干净的行数。
用代码块功能插入代码,请勿粘贴截图
#include<stdio.h>
void bubble_sort(int* p, int len)//函数实现
{
int i = 0;
int j = 0;
for (i = 0; i < len - 1; i++)//需要进行len-1趟
{
int flag = 1;//flag=1,说明已经排好序
for (j = 0; j < len - 1 - i;j++)//每趟两两比较较未排好序元素个数-1次。
{
if (p[j] < p[j+1])
{
int tmp = p[j];
p[j] = p[j + 1];
p[j + 1] = tmp;
flag = 0;
}
}
if (flag==1)//判断是否排好序
break;
}
}
int main()
{
int n,i,j,x,y=0;
scanf(“%d”,&n);
int a[n][n],b[n]=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf(“%d”,a[i][j]);
if(a[i][j]==0)
b[i]++;
}
}
scanf(“%d”,&x);
bubble_sort(b,n);
for (i = 0; i < x; i++)
{
y=y+b[x];
}
printf("%d\n",y/5);
return 0;
}
}
运行结果及报错内容
输入n=5,x=3;
矩阵
10011
01100
10100
01010
00011
输出y=1
我的解答思路和尝试过的方法
使用冒泡排序,找出0最多的列进行打扫,使最后干净的行数最多。
但是好像太复杂了,编程不完善。
我想要达到的结果
输出完全干净的最大行数。