UVa 12545 Bits Equalizer——贪心

UVa 12545 Bits Equalizer——贪心

先把能交换的交换了，尽量交换，然后进行数字的变换，变换过程中遇到1 到 0直接输出-1；

变换过程好说，交换过程要考虑的情况比较多

首先把具体的数字进行交换，二层循环

然后把带问号的数字进行交换，具体怎么交换看代码，又是二层循环

最后一层循环解决变换问题

最终复杂度为O(n^2)

#include #include #include #include using namespace std;char a[200], b[200];int n, ans;int main(){ int T, flag = 0; scanf("%d", &T); getchar(); while (T--) { gets(a); gets(b); n = strlen(a); ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j == i) continue; if (a[i] == b[j] && b[i] == a[j] && a[i] != b[i]) { swap(a[i], a[j]); ans++; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j == i) continue; if (a[i] == '1' && b[i] == '0' && b[j] == '1' && a[j] != '1') { swap(a[i], a[j]); ans++; } else if (a[i] == '0' && b[i] == '1' && a[j] == '?' && b[j] == '0') { swap(a[i], a[j]); ans++; } } } bool ok = true; for (int i = 0; i < n; i++) { if (a[i] == '1' && b[i] == '0') { ok = false; break; } if (a[i] == '?') { a[i] = b[i]; ans++; } else if (a[i] == '0' && b[i] == '1') { a[i] = b[i]; ans++; } } if (!ok) ans = -1; printf("Case %d: %d\n", ++flag, ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。