🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1055

🌍 评测功能需要 订阅专栏 后私信联系清隆解锁～

🍓OJ题目截图

🍡 K小姐的座位分配

问题描述

在一场大型活动中，为了满足疫情防控的要求，主办方要求观众入座时必须间隔至少一个空位。现在给出一排观众座位的分布情况，请计算在不移动已入座观众的前提下，最多还可以安排多少观众入座。

输入格式

输入一个字符串，其中 $0$ 表示该座位没有观众，$1$ 表示该座位已有观众入座。字符串长度范围为 $[1,10000]$。

输出格式

输出一个整数，表示在不移动已入座观众的情况下，最多还能安排的观众数量。

样例输入

10001

样例输出

1

样例输入

0101

样例输出

0

数据范围

$1\le 字符串长度\le 10000$

题解

为了最大化新安排的观众数量，我们可以使用贪心策略，从左到右检查每个座位。如果当前座位和相邻的左右座位都为空，则可以在此座位安排观众，并将其标记为已占用，以避免违反间隔规则。

参考代码

• Python

def main():
    seats = input().strip()
    count = 0
    i = 0
    while i < len(seats):
        if seats[i] == '0' and (i == 0 or seats[i - 1] == '0') and (i == len(seats) - 1 or seats[i + 1] == '0'):
            count += 1
            # Mark this seat as taken to avoid violating the rules.
            if i < len(seats) - 1:
                seats = seats[:i] + '1' + seats[i+1:]
            else:
                seats = seats[:i] + '1'
            i += 2  # Move two places forward to ensure the spacing rule
        else:
            i += 1
    print(count)

if __name__ == "__main__":
    main()

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String seats = scanner.nextLine();
        int count = 0;
        for (int i = 0; i < seats.length(); i++) {
            if (seats.charAt(i) == '0' && (i == 0 || seats.charAt(i - 1) == '0') && (i == seats.length() - 1 || seats.charAt(i + 1) == '0')) {
                count++;
                if (i < seats.length() - 1) {
                    seats = seats.substring(0, i) + '1' + seats.substring(i + 1);
                } else {
                    seats = seats.substring(0, i) + '1';
                }
                i++;  // Move forward to ensure the spacing rule
            }
        }
        System.out.println(count);
    }
}

• Cpp

#include <iostream>
#include <string>
using namespace std;

int main() {
    string seats;
    cin >> seats;
    int count = 0;
    for (int i = 0; i < seats.size(); i++) {
        if (seats[i] == '0' && (i == 0 || seats[i - 1] == '0') && (i == seats.size() - 1 || seats[i + 1] == '0')) {
            count++;
            seats[i] = '1';  // Mark this seat as taken to avoid violating the rules.
        }
    }
    cout << count << endl;
    return 0;
}