题目描述

给定一个定长停车场，用整型字符串数组$cars$表示车位占用情况，其中$1$表示有车，$0$表示空位。车辆有三种尺寸：小车占据长度$1$，货车占据长度$2$，卡车占据长度$3$。请统计在当前停放状况下，停车场最少可以停多少辆车，并返回该最小车数。

思路

1. 将数组拆分为若干段连续的“有车区间”，每个区间长度记为$L$。
2. 对于每个长度为$L$的区间，要用尺寸为$3,2,1$ 的车来覆盖，使得车辆总数最少。
3. 这是一个经典的“凑零钱”最少硬币问题，面值为$3,2,1$，对于此面值体系，贪心算法（优先使用最大面值）可得到最优解。
4. 因此，对于每个区间，车辆数可按以下公式计算：
5. 将所有区间的 $\text{count}$ 累加，即为答案。

C++

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

int minVehicles(const vector<int>& cars) {
    int n = cars.size();
    int result = 0;
    int i = 0;
    while (i < n) {
        // 找到下一个连续1段的起点
        if (cars[i] == 1) {
            int len = 0;
            // 统计连续1的长度 len
            while (i < n && cars[i] == 1) {
                len++;
                i++;
            }
            // 对长度 len 使用贪心计算最少车辆数
            result += len / 3;               // 使用卡车数量
            int rem = len % 3;
            result += rem / 2;               // 使用货车数量
            result += rem % 2;               // 使用小车数量
        } else {
            i++;
        }
    }
    return result;
}

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<int> cars;
    int x;
    char comma;
    // 读取以逗号分隔的输入
    while (ss >> x) {
        cars.push_back(x);
        ss >> comma;
    }
    cout << minVehicles(cars) << endl;
    return 0;
}

Python

def min_vehicles(cars):
    n = len(cars)
    result = 0
    i = 0
    while i < n:
        if cars[i] == 1:
            length = 0
            while i < n and cars[i] == 1:
                length += 1
                i += 1
            # 贪心选取：先用尽可能多的3，再是2，最后1
            result += length // 3
            rem = length % 3
            result += rem // 2
            result += rem % 2
        else:
            i += 1
    return result

if __name__ == "__main__":
    line = input().strip()
    cars = list(map(int, line.split(',')))
    print(min_vehicles(cars))

Java

import java.util.*;

public class Main {
    public static int minVehicles(int[] cars) {
        int n = cars.length;
        int result = 0;
        int i = 0;
        while (i < n) {
            if (cars[i] == 1) {
                int len = 0;
                while (i < n && cars[i] == 1) {
                    len++;
                    i++;
                }
                // 按长度 len 贪心分配 3, 2, 1
                result += len / 3;
                int rem = len % 3;
                result += rem / 2;
                result += rem % 2;
            } else {
                i++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] parts = line.split(",");
        int[] cars = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            cars[i] = Integer.parseInt(parts[i]);
        }
        System.out.println(minVehicles(cars));
    }
}

题目描述

特定大小的停车场，数组 $cars$[]表示，其中 $1$ 表示有车， $0$表示没车。车辆大小不一，小车占一个车位(长度 $1$ )，货车占两个车位(长度 $2$)，卡车占三个车位(长度 $3$)，统计停车场最少可以停多少辆车，返回具体的数目。

输入描述

整型字符串数组 $cars$，其中 $1$ 表示有车，$0$ 表示没车，数组长度小于 $1000$。

输出描述

整型数字字符串，表示最少停车数目。

样例1

输入

1,0,1

输出

2

说明：$1$ 个小车占第 $1$ 个车位，第二个车位空，$1$ 个小车占第 $3$ 个车位最少有两辆车。

样例2

输入

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

输出

3

说明：$1$ 个货车占第 $1$、 $2$ 个车位，第 $3$ 、$4$ 个车位空

​ $1$ 个卡车占第 $5$ 、$6$ 、$7$ 个车位

​ 第 $8$ 个车位空

​ $1$ 个小车占第 $9$ 个车位最少 $3$ 辆车