题解：CF2225C Red-Black Pairs

· · 题解

一道简单贪心。

Solution

从第 1 列开始处理，设当前处理到第 i 列。

若上下颜色相同直接将这两个格子垂直配对，无需修改任何颜色，随后处理下一列。

若上下颜色不同，此时有两种选择：

  1. 垂直配对：修改当前列中一个格子的颜色使它们相同，花费 1 次修改，然后处理下一列。
  2. 水平配对（与下一列组合）：将第 i 列与第 i+1 列作为一个整体，第一行的 i 与 i+1 左右配对，第二行的 i 与 i+1 左右配对。

为了最小化修改次数，我们比较两种选择的代价：

如果无法使用水平配对，即已经是最后一列，则只能垂直配对。如果可以水平配对，且至少有一行的相邻颜色相同，那么水平配对的总花费 \le 1，不劣于垂直配对的花费 1，因此选择水平配对。

如果两行的相邻颜色都不相同（水平配对花费为 2），则垂直配对更优（花费 1）。

按照上述策略贪心扫描一遍即可得到答案。

至于正确性：对于每一列，若上下同色则直接配对显然最优；若上下不同色，选择与下一列组合还是单独配对只影响当前和下一列的状态，不会对更右侧的列造成负面限制。同时因为水平配对总是成对消耗两列，不存在半个水平对的情况，所以贪心选择具有无后效性。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int T,n;
char a[N][2];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i][0];
        }
        for(int i=1;i<=n;i++){
            cin>>a[i][1];
        }
        int ans=0,cn=1;
        while(cn<=n){
            if(a[cn][0]==a[cn][1])cn++;
            else if(cn==n||(a[cn][0]!=a[cn+1][0]&&a[cn][1]!=a[cn+1][1])){
                cn++;
                ans++;
            }
            else {
                if(a[cn][0]!=a[cn+1][0])ans++;
                if(a[cn][1]!=a[cn+1][1])ans++;
                cn+=2;
            }
        }
        cout<<ans<<'\n';
    }
}