Google KickStart之翻煎饼
题目的大致意思就是读取一个文件,在文件的第一行输入文件的行数,然后读取这些数据,在每一行的数据中第一部分由一个由+(happy side)/-(blank side)组成的字符串,
每一行数据的第二部分为一个整型变量,表示每次可以翻面的个数,且每次翻面必须为这个个数,那么如果可以将这些煎饼全部翻面成为+(happy side)向上,则打印出需要翻面
的次数,否则打印出"IMPOSSIBLE".
官方给出的解题思路是通过判断可以选择放铲子的地方一共由N-K+1,其中N为第一行中字符串的长度,K为第一行中整数的值(即每次翻面的煎饼的个数),
在官网download了一份加拿大ACM选手的答案(C++版本,感觉做算法还是C++好),在题目中遍历的过程中遍历的取值范围即为for(j=0;j+K-1<N;j++),
因为每次翻面的煎饼的个数为K,所以每次需要调整K个煎饼的状态,for(int m=0;m<K;m++),这里出现了一个一开始很费解,理解之后觉得很神奇的地方:
chars[j+m] ^='-'^'+'(这里是我用Java语言复现的结果,原来版本的代码为str[i+j] ^='-'^'+'),这里利用了抑或相互抵消的原理,将原来的状态变为相反的状态;
至于在官网解析中提到的可以用一个count标志位来计数,每次计数到奇数则将count加1,如果计数到偶数,则将count减1,这个操作还是不甚理解
(通过这种方式来减少时间复杂度,原本的时间复杂度为O(n^2),改进以后为O(n)???).