P76024 四人座车辆 — 题解

专题： 排序与贪心
适用题目： 新生 OJ 本地题包中的 P76024，不要直接用于外站同名题。

解题思路

4 人组单独一车；3 人组尽量配 1 人组；2 人组两两合并，剩余的 2 人组尽量搭 1 人组；最后处理剩余 1 人组。

复杂度

时间 $O(n)$，额外空间 $O(1)$。

易错点

先安排大组，再填剩余座位，避免把小组错误拆分。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int max_int(int a,int b){return a>b?a:b;}
int main(void) {
    int n,c[5]={0};scanf("%d",&n);
    for(int i=0;i<n;i++){int x;scanf("%d",&x);c[x]++;}
    int ans=c[4]+c[3];
    c[1]=max_int(0,c[1]-c[3]);
    ans+=c[2]/2;
    if(c[2]%2){ans++;c[1]=max_int(0,c[1]-2);}
    ans+=(c[1]+3)/4;
    printf("%d\n",ans);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    int c[5]={
    }
    ;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        c[x]++;
    }
    int ans=c[4]+c[3];
    c[1]=max(0,c[1]-c[3]);
    ans+=c[2]/2;
    c[2]%=2;
    if(c[2]){
        ans++;
        c[1]=max(0,c[1]-2);
    }
    ans+=(c[1]+3)/4;
    cout<<ans<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。