有一个 n 行 m 列的 01 矩阵,每一次操作都可以选择一列然后把这一列的所有数字翻转,翻转即 0 变成 1 ,1 变成 0。
如果你要操作恰好 K 次,问最后最多能让多少行满足这一行所有数字都是 1 ?
有一个 n 行 m 列的 01 矩阵,每一次操作都可以选择一列然后把这一列的所有数字翻转,翻转即 0 变成 1 ,1 变成 0。
如果你要操作恰好 K 次,问最后最多能让多少行满足这一行所有数字都是 1 ?
每组测试用例仅包含一组数据,每组数据第一行为三个整数 n , m , K (1 ≤ n,m ≤ 50 , 0 ≤ K ≤ 1000) , 接下来有 n 行每行有一个长度为 m 的 0/1 字符串表示第 i 行的数字。
输出一个数,代表你最多能使得多少行在恰好 K 次操作后全是 1。
对于输入样例,翻转第2列后后两行都是1。
3 2 1 01 10 10
2
思路: 首先统计矩阵各行0的个数,保存在数组rsum中,第i行0的个数记作rsum[i]。若接下来 要对矩阵进行K次反转,对第i行来说,当且仅当K>=rsum[i]且K与rsum[i]同奇偶时,才有可 能在K次反转后将第i行变为全1行。 在此基础之上,使用贪心策略模拟K次反转。对于每一次反转,对满足K>=rsum[i]且K与 rsum[i]同奇偶的行,统计每列0的个数,选择其中0个数最多的列进行反转。如此进行K次, 求最终结果矩阵的全1行数,即得最终结果。 举例来说,对测试用例: 6 5 3 1 0 0 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 3次翻转过程如下: (1)计算各行0的个数,得到rsum = [3, 3, 2, 3, 2, 3],此时K = 3,满足K>=rsum[i] &&(K%2==rsum[i]%2)的行分别为[0, 1, 3, 5],第[0, 1, 3, 5]行组成的子矩阵为: 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 求该子矩阵中各列0的个数,得到csum = [1, 2, 4, 2, 3],其中0个数最多的为第2列(下 标从0开始计算),因此将原矩阵第2列进行1次反转,K = 3 - 1 = 2,得到新矩阵: 1 0 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 (2)计算各行0的个数,得到rsum = [2, 2, 3, 2, 3, 2],此时K = 2,满足K>=rsum[i] &&(K%2==rsum[i]%2)的行分别为[0, 1, 3, 5],第[0, 1, 3, 5]行组成的子矩阵为: 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 求该子矩阵中各列0的个数,得到csum = [1, 2, 0, 2, 3],其中0个数最多的为第4列, 因此将原矩阵第4列进行1次反转,K = 2 - 1 = 1,得到新矩阵: 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 1 (3)计算各行0的个数,得到rsum = [1, 1, 2, 3, 4, 1],此时K = 1,满足K>=rsum[i] &&(K%2==rsum[i]%2)的行分别为[0, 1, 5],第[0, 1, 5]行组成的子矩阵为: 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 求该子矩阵中各列0的个数,得到csum = [0, 1, 0, 2, 0],其中0个数最多的为第3列, 因此将原矩阵第3列进行1次反转,K = 1 - 1 = 0,得到新矩阵: 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 此时K=0,K次反转已经全部用完,计算结果矩阵全1行的个数,得到最终结果为2。 附代码如下:#include <iostream> using namespace std; int mat[51][51]; //记录0/1矩阵 int rsum[51]; //记录每行0的个数 int csum[51]; //记录每列0的个数,仅计算0的个数小于等于K且与K同奇偶的行 char str[51]; int main() { int N, M, K; while (cin >> N >> M >> K) { for (int i = 0; i < N; ++i) { cin >> str; for (int j = 0; j < M; ++j) mat[i][j] = str[j] - '0'; } while (K) {//模拟反转K次 for (int i = 0; i < N; ++i) {//计算每行0的个数 rsum[i] = 0; for (int j = 0; j < M; ++j) if (mat[i][j] == 0) rsum[i]++; } for (int j = 0; j < M; ++j) {//计算每列0的个数 csum[j] = 0; for (int i = 0; i < N; ++i) if (K >= rsum[i] && (rsum[i] % 2) == (K % 2) && mat[i][j] == 0)//仅计算0个数小于等于K且与K同奇偶的行 csum[j] ++; } //找到0的个数最大的列 int max = -1, mpos = -1; for (int j = 0; j < M; ++j) if (csum[j] > max) { max = csum[j]; mpos = j; } //列反转一次 for (int i = 0; i < N; ++i) mat[i][mpos] = (mat[i][mpos] == 0) ? 1 : 0; K--; } int ans = 0; for (int i = 0; i < N; ++i) { int one_num = 0; for (int j = 0; j < M; ++j) if (mat[i][j] == 1) one_num++; if (one_num == M) ans++; } cout << ans << endl; } return 0; }