Ama no Jaku

登录—专业IT笔试面试备考平台_牛客网

题目大意：有一个n*n且仅由0和1构成的矩阵，每次操作可以将一整行或一整列的所有数取反，问能否使所有行中构成的最小数>=所有列中构成的最大数

1<=n<=2000

思路：首先，如果要使最小数>=最大数，唯一满足的情况就是矩阵中所有数都等于0或都等于1，然后我们从最终状态往回操作试试，可以发现，无论我们操作多少次，所有行最多构成两个不同的数字，且这两个数字是互补的，要统计最小值，只需从这两个中找出数量最少的那一个，然后统计出期中数量最少的，就等于对行的操作数，再统计那个数字中0和1哪个最少，就等于列的操作数

#include<bits/stdc++.h>
using namespace std;int n,i,j,x,ans1,ans2,w;
string f[2010],s[2010];
map<string,int> m;int main(){cin>>n;for (i=0;i<n;i++){cin>>s[i];}for (i=0;i<n;i++) if (m[s[i]]==0) {for (j=i;j<n;j++) if (s[i]==s[j]) {if (m[s[i]]==0){m[s[i]]=1;x++;//统计所有行中有几个不同的数字f[x]=s[i];} else m[s[i]]=m[s[i]]+1;}}if (x>2) printf("-1");//多于2种肯定无法达成题目要求else if (x==1){for (i=0;i<n;i++){if (s[0][i]=='1') ans1++;//统计这个数字中1的数量}printf("%d",min(ans1,n-ans1));//1和0的数量取最小值} else {for (i=0;i<n;i++) if (f[1][i]==f[2][i]){printf("-1");//两个不同的数字一定是互补的return 0;}ans1=m[f[1]];for (i=0;i<n;i++) if (f[1][i]=='0') w++;ans1=ans1+min(w,n-w);w=0;//分别统计两个数字中1和0的数量的最小值ans2=m[f[2]];for (i=0;i<n;i++) if (f[2][i]=='0') w++;ans2=ans2+min(w,n-w);printf("%d",min(ans1,ans2));}return 0;
}