Editorialist: PHPeasant, Tommoa

Maxi Taxi requires you to find how many taxis are needed to cart our compatriots to Cameron Hall. The main observation to make is that we only need the number of taxis and not a specific solution. This suggests we could simply try to fill as many taxis as possible in a greedy fashion; which is correct. We can trivially fill as many cars as groups of four as possible. We match groups of threes with as many groups of ones as possible. Then twos with twos, twos with ones and finally ones with ones. Any remaining group will ride in their own car.

An example implementation in C++14 is given below:

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    array<int, 4> cars = { 0, 0, 0, 0 };
    for (int i = 0; i < N; ++i) {
        int t;
        cin >> t;
        ++cars[t-1];
    }
    cars[3] += cars[2];
    cars[0] = max(0, cars[0] - cars[2]);
    cars[3] += cars[1] >> 1;
    if ((cars[1]) & 1) {
        cars[3] += 1;
        cars[0] = max(0, cars[0] - 2);
    }
    cars[3] += (cars[0] >> 2) + (cars[0] % 4 > 0);

    cout << cars[3] << '\n';
}