#P14230. 停车场车辆统计(100分)
-
1000ms
Tried: 39
Accepted: 20
Difficulty: 5
所属公司 :
华为od
-
算法标签>贪心
停车场车辆统计(100分)
题目描述
给定一个定长停车场,用整型字符串数组cars表示车位占用情况,其中1表示有车,0表示空位。车辆有三种尺寸:小车占据长度1,货车占据长度2,卡车占据长度3。请统计在当前停放状况下,停车场最少可以停多少辆车,并返回该最小车数。
思路
- 将数组拆分为若干段连续的“有车区间”,每个区间长度记为L。
- 对于每个长度为L的区间,要用尺寸为3,2,1 的车来覆盖,使得车辆总数最少。
- 这是一个经典的“凑零钱”最少硬币问题,面值为3,2,1,对于此面值体系,贪心算法(优先使用最大面值)可得到最优解。
- 因此,对于每个区间,车辆数可按以下公式计算:

- 将所有区间的 $\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 辆车