贝壳找房 · 贪心 · 算法编程题
贝壳找房 贪心 n ≤ 1e5 时限 1 秒 / 128 MB

题目描述

牛牛有 2n 块地板砖构成一个 2× n 的矩阵，即地板砖摆成两行 n 列。第一行每块地板砖的颜色用一个长度为 n 的字符串 a 表示，第二行每块地板砖的颜色用一个长度为 n 的字符串 b 表示，字符`0`表示黑色，字符`1`表示白色，牛牛想对其中一些地板砖重新染色，使得任意相邻两列地板砖恰好有 2 个黑色地板砖和 2 个白色地板砖，问最少需要对多少地板砖染色。

输入输出

输入描述
第一行，一个整数 n(2≤ n ≤ 10^5) 。
第二行，一个长度为 n 的字符串 a ， a_i 为`0`或`1`。
第三行，一个长度为 n 的字符串 b ， b_i 为`0`或`1`。
输出描述
输出一行一个整数表示牛牛最少需要对多少地板砖重新染色，使得任意相邻两列地板砖恰好有 2 个黑色地板砖和 2 个白色地板砖。

样例共 1 组

样例 1 · 将第二行第一个地板砖染成黑色： 110 001
输入
3
110
101
输出
1

算法解析依据充分

考点：贪心

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 128MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e5
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

本题切入点

逐列看两列的 01 组合，把不满意的列统一调整为「两黑两白」，按列递推统计最小改动数。

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

  1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
  2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
  3. 按策略一次扫描（通常要先排序）得到答案。
  4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做（典型错因）。
  • 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。

样例解读

样例 1：输入 3 / 110 / 101 → 输出 1

将第二行第一个地板砖染成黑色：

110

001

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招测试类试卷。

‹ 上一题 全部编程题
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解