有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
输入 两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。 输出 至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。 样例输入 011 000样例输出
1
首先先附上我AC的代码：
#include<iostream> #include<cstring> using namespace std; void change(char &a) { if(a=='0') a='1'; else if(a=='1') a='0'; else return ; } int main() { char a1[33],a2[33],b[33]; cin>>a1; cin>>b; int n=strlen(a1); strcpy(a2,a1); int sum1=1,sum2=0; change(a1[0]); change(a1[1]); for(int i=0;i<n-1;i++) //假设第一次按了第一个键 { int j=i; if(a1[i]!=b[i]) { sum1+=1; change(a1[++j]); change(a1[++j]); } } if(a1[n-1]!=b[n-1]) sum1=-1; for(int i=0;i<n-1;i++) //假设第一次未按第一个键 { int j=i; if(a2[i]!=b[i]) { sum2+=1; change(a2[++j]); change(a2[++j]); } } if(a2[n-1]!=b[n-1]) sum2=-1; if(sum1 ==sum2 && sum1 == -1) // 执行判断 cout<<"impossible"; else { if(sum1 == -1 || sum2 == -1) cout<<(sum1 > sum2 ? sum1 : sum2); else cout<<(sum1 < sum2 ? sum1 : sum2); } } 然后讲一下我做这题的思路。
因为题目中描述按一个键改变自身和相邻的键。枚举的时间复杂度太高，肯定是TLE，所以我采用的是贪心算法，保证前面的键先全部符合，再去看能否让最后一个键匹配到，如果匹配就表示可行，输出改变的次数sum。
用for循环的模式判断a[i]与b[i]是否能对应，能对应就继续。不能对应就改变a[i]后两个键，这样的做法相当于按了a[i+1]，不用考虑a[i]本身的原因是直接i++就能跳过对a[i]的判断。
然后提交。
WA。
回去看了下代码，发现确实少考虑了一个情况。a[0]在题目中有特殊的地位——按下a[0]时仅改变之后的一个键，而改变a[0]的方法有两种，一种是按a[0]，另一种是按a[1]，这两种方法都不会影响之前数组的匹配。甚至说是先按a[0]、再按a[1]都能使a[0]保持原样而影响之后的数组，所以不论a[0]与b[0]是否匹配，a[0]按和不按的情况都要考虑。
因此我把这种情况考虑进去。由于是change()是直接对数组中的数修改，所以我另开一个数组保存a，又另开一个sum统计变量。之后的判断情况也进行了修改：如果第一次按了a[0]，最后结果不能匹配则返回-1。
最后的输出判断也改成，如果两个-1，那么输出impossible；哪个不是-1就输出哪一个。（因为这两种情况不会同时实现）
修改完以后提交。
成功AC。
