题意:
有n头奶牛排成一排,有的朝前(F)有的朝后(B),现在你可以使k头奶牛一次性翻转朝向(n>=k>=1),问你最少的翻转次数和此时对应的k值。
Input
Line 1: A single integer: N Lines 2.. N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.
Output
Line 1: Two space-separated integers: K and M
Sample Input
7
B
B
F
B
F
B
B
Sample Output
3 3
Analysis
我们先来观察,可以发现,处理好i前面的点后,如果i这个点是B的话,就必须反向,而反向一次以上的话,是无效的(奇数次与1次等效,偶数次于0次等效)。
所以我们可以枚举K,然后从1处理到N,如果需要处理,就再套一个循环修改。这样的复杂度是O(N3),仍然不够。
我们想,如果这个数加上[i-k+1,i-1]的翻转次数,是奇数的话就代表需要切换,然后记录下区间次数和sum每次加上新处理的点,去掉即将在区间外的点。这样,就降到N2 了
Code
1 #include<set>
2 #include