rt,这个思路不能过大样例,会在对应的 #13 和 #19 WA 掉。(也就是说大概 60pts)
我的思路是对于每个连续而相同的 t1,i 块和 t2,i 块(如样例1中 t1,1∼t1,3 都为 1,t1,4∼t1,4 都为 0,就分别为两个个块),然后按照分的块贪心。
贪心思路是:对于每个两个块(t1 和 t2 的),如果两个块中都是 0,直接暴力比对一样的个数,否则取两个块中 0 的个数的最小值和 1 的个数的最小值加到答案里,并将两个块中 0 和 1 的数量都减去这两个最小值(因为拿去匹配了,后面不会用到)。
下一步就是比较两个块的右边界谁更前,将更前的块的指针指向下一个块(比如 [1,3](t1的) 和 [2,2](t2的) 比对时,将指向 t2 的块的指针后移一个,即使其指向下一个块 )
最终当有一个 t 的块被匹配完时就输出答案。
具体代码暂时先不给,(没时间重写了,赛时写200行好难写回来)