华为OD机试 - 体育场找座位（Java 2024 C卷 100分）

待我称王封你为后i 2024-05-28 10:25 83阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

在一个大型体育场内举办了一场大型活动，由于疫情防控的需要，要求每位观众的必须间隔至少一个空位才允许落座。现在给出一排观众座位分布图，座位中存在已落座的观众，请计算出，在不移动现有观众座位的情况下，最多还能坐下多少名观众。

### 二、输入描述 ###

一个数组，用来标识某一排座位中，每个座位是否已经坐人。0表示该座位没有坐人，1表示该座位已经坐人。

### 三、输出描述 ###

整数，在不移动现有观众座位的情况下，最多还能坐下多少名观众。

#### 1、输入 ####

10001

#### 2、输出 ####

### 四、解题思路 ###

为了解决这个问题，我们可以遍历一遍座位数组，用贪心算法来确定每个可用座位。主要思想是：如果当前座位是空的（即值为0）并且左边的座位是空的或者该座位是数组的第一个位置，我们就可以在这个位置安置一位观众。同时，我们需要确保在这位观众的右侧也至少有一个空位（除非该观众坐在数组的最后一个位置）。

实现步骤

1.  遍历座位数组。
2.  对于每个座位，检查其是否为空。
3.  如果为空，并且左侧没有人或是数组的第一个位置，尝试在此位置坐人。
4.  落座后，跳过下一个座位（确保至少一个空位的间隔）。
5.  继续检查下一个未检查的座位。

### 五、Java算法源码 ###

public class OdTest01 {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String input = sc.nextLine();
            int[] seats = input.chars().map(c -> c - '0').toArray();
            int n = seats.length;
            int count = 0; // 用于计数可以增加的观众数
    
            for (int i = 0; i < n; i++) {
        
                if (seats[i] == 0) {
         // 当前座位为空
                    // 检查左右是否满足坐人条件
                    boolean canSeat = (i == 0 || seats[i - 1] == 0) && (i == n - 1 || seats[i + 1] == 0);
                    if (canSeat) {
        
                        count++;
                        seats[i] = 1; // 标记此位置已有观众坐下
                        i++; // 跳过下一个座位，保证间隔
                    }
                }
            }
    
            System.out.println(count);
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

0101

#### 2、输出 ####

![在这里插入图片描述][ec869b2365f44cb0a7c934d872f17349.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/268b568445fd48f3929076d7ffe6107f.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[ec869b2365f44cb0a7c934d872f17349.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/03461dfe76f2488c8085b21758387779.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/28/2a9ed3a9668845eb8263e27bf596399d.gif