最新华为OD机试真题-停车场车位统计(100分)

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

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

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> 停车场车位统计(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

停车场车位统计

题目描述

K小姐经营着一个特定大小的停车场，停车场可以看成一个数组 ，其中 表示有车， 表示没车。现在停车场内停放着大小不一的车辆，其中小车占一个车位(长度 )，货车占两个车位(长度 )，卡车占三个车位(长度 )。

K小姐想知道，按照当前停车场的停放情况，最少有多少辆车停在停车场内。你能帮帮她吗？

输入描述

输入一个由 和 组成的字符串，以逗号分隔，表示停车场的车位情况。其中 表示有车， 表示没车，字符串长度不超过 。

输出描述

输出一个整数，表示停车场内最少的停车数目。

样例1

输入

1,0,1

输出

2

说明： 个小车占第 个车位，第 个车位空， 个小车占第 个车位，最少有 辆车。

样例2

输入

1,1,0,0,1,1,1,0,1

输出

3

说明： 个货车占第 、 个车位，第 、 个车位空， 个卡车占第 、、 个车位，第 个车位空， 个小车占第 个车位，最少有 辆车。

数据范围

题解

本题可以使用贪心算法来解决。我们可以从左到右遍历停车场的车位情况，每次尽可能地停放一辆大的车。

具体地，我们维护一个变量 ，表示当前已经停放的车辆数。同时，用变量 表示当前遍历到的位置。

在遍历过程中，如果当前位置为 ，说明没有车，直接跳过。如果为 ，我们就尝试停放一辆车。首先判断能否停放一辆卡车，即 、、 这三个位置都为 。如果可以，就停一辆卡车， 加 ， 向后移动 个位置。如果不能停卡车，就判断能否停货车，即 、 这两个位置都为 。如果可以，就停一辆货车， 加 ， 向后移动 个位置。如果也不能停货车，那只能停一辆小车， 加 ， 向后移动 个位置。

遍历结束后， 的值就是停车场内最少的停车数目。

参考代码

• Python

cars = input().split(',')
n = len(cars)
cnt = 0
i = 0
while i < n:
    if cars[i] == '1':
        if i+2 < n and cars[i+1] == '1' and cars[i+2] == '1':
            cnt += 1
            i += 3
        elif i+1 < n and cars[i+1] == '1':
            cnt += 1
            i += 2
        else:
            cnt += 1
            i += 1
    else:
        i += 1
print(cnt)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] cars = sc.next().split(",");
        int n = cars.length;
        int cnt = 0;
        for (int i = 0; i < n; ) {
            if (cars[i].equals("1")) {
                if (i+2 < n && cars[i+1].equals("1") && cars[i+2].equals("1")) {
                    cnt++;
                    i += 3;
                } else if (i+1 < n && cars[i+1].equals("1")) {
                    cnt++;
                    i += 2;
                } else {
                    cnt++;
                    i++;
                }
            } else {
                i++;
            }
        }
        System.out.println(cnt);
    }
}

• Cpp

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

int main() {
    string str;
    cin >> str;
    int n = str.size();
    int cnt = 0;
    for (int i = 0; i < n; ) {
        if (str[i] == '1') {
            if (i+2 < n && str[i+1] == '1' && str[i+2] == '1') {
                cnt++;
                i += 3;
            } else if (i+1 < n && str[i+1] == '1') {
                cnt++;
                i += 2;
            } else {
                cnt++;
                i++;
            }
        } else {
            i++;
        }
    }
    cout << cnt << endl;
    return 0;
}