P8301 [CoE R4 A/Stoi2041] 娘子 题解

Tz_Obopn233 · 2022-04-27 11:59:27 · 题解

这道题一开始没仔细去读，结果用了动态规划（怎么第一题就这么难啊）。

做了半天才发现，序列 a 在取反之后是可以任意排列的……

我们令 d_1 为序列 a 出现 0 的个数，d_2 为序列 b 出现 0 的个数。那么，n\! - \!d_1 就是序列 a 出现 1 的个数，n\! - \!d_2 就是序列 b 出现 1 的个数。

题目要求我们用最小的次数完成 a_i=b_i，那么方法无非两种：d_1\! = \!d_2 或 n\! - \!d_1\! = \!n\! -\!d_2。

那么，更改的次数应该为 |d_1\!-\!d_2| 或 |n\!-d_1\!-\!(n-d_2)|。

为什么呢？我们可以化简其中一个式子：

而因为 |d_1\!-\!d_2| 等于 |d_2\!-\!d_1|，那么，更改 1 的次数就等于更改 0 的次数，我们根本无需比较！

我们可以只统计 0 或 1 在序列 a,b 中出现的次数，它们之差的绝对值就是最小的次数。

Code：

#include<bits/stdc++.h>
using namespace std;
int n,d1,d2;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        char x; cin>>x;
        if(x=='0') d1++;//d1记录a中出现0的次数 
    }
    for(int i=1;i<=n;i++) {
        char x; cin>>x;
        if(x=='0') d2++;//d2记录b中出现0的次数 
    }
    printf("%d",(abs(d1-d2)));//由于|d1-d2|=|n-d1-(n-d2)|，我们无需比较，直接输出就行了 
    return 0;
}