题解：AT_dwango2017qual_c スキーリフトの相乗り

LotleTos · 2025-11-02 19:34:28 · 题解

由于每个人都要上车，改变顺序时最优答案不变，所以可以不考虑顺序。

要想车数量最少，那么每辆车就要尽可能利用，也就是要坐最多人。

由于每队人数最多为四，最少为一，故可以统计每种人数的队伍数量，记为 a1，a2，a3，a4。

分别考虑：

code

#include<bits/stdc++.h>
using namespace std;
int a[5];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a[x]++;
    }
    int ans=a[4];
    ans+=a[3];
    a[1]-=min(a[3],a[1]);
    ans+=a[2]/2;
    if(a[2]%2){
        ans++;
        if(a[1]>=1){
            a[1]-=min(a[1],2);
        }
    }
    ans+=(a[1]+3)/4;
    cout<<ans<<endl;
}