Codeforces - 1037C - Equalize

Question

题目大意

就是给你两个字符串 a 、 b ， 都是二进制串 01 组成，要你用下面的两种方式把字符串 a 变成字符串 b （ b 不能修改）:

• 交换 a 的两个索引 i 、 j 的值，花费 abs(i - j) ；
• 将 a 的 i 位置翻转( 0 变 1 ， 1 变 0 )， 花费 1 ；

要你求最少的花费。

解析

一开始看标签是 dp ，想了一会好像就是一个贪心，因为如果 i ， j 距离超过 2 (不是相邻)，那就没什么用了。所以只需要求出所有不同的个数，减去相邻可以交换的个数就可以了。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        String a = cin.next();
        String b = cin.next();
        int diff = 0;
        for(int i = 0; i < a.length(); i++)
            if(a.charAt(i) != b.charAt(i))
                diff++;
        int adjacent = 0;
        for(int i = 0; i < a.length()-1; i++){
            if(a.charAt(i) == b.charAt(i))
                continue;
            if(a.charAt(i+1) != b.charAt(i+1) && a.charAt(i) != a.charAt(i+1)){
                    adjacent++;
                    i++;
            }
        }
        System.out.println(diff-adjacent);
        
    }
}