Codeforces B. Taxi 算法题解

Codeforces B. Taxi 算法题解2015-02-25简单总结题意：

有一个数组，数组中的数值不会大于4，即只能是1,2,3,4，要把这些数值装进一个容量最大为4的容器里面，使得所用到这样的容器的个数最小。

经测试数据很大，会有10万个数据，所以这里我并不用排序数据，而是使用counting sort的思想，根据特定的数据优化，使得题解时间复杂度为O（n）。

程序如下：

#include <iostream>#include <vector>#include <string>#include <ctype.h>using namespace std;void Taxi（）{int n = 0;cin>>n;int nums = 0;int A[3] = {0};int a = 0;for （int i = 0; i < n; i++）{cin>>a;if （4 == a） nums++;else A[a-1]++;}nums += A[1] / 2;A[1] %= 2;if （A[0] <= A[2]） {nums += A[0];A[2] -= A[0];if （A[1]） nums++;nums += A[2];}else{nums += A[2];A[0] -= A[2];nums += A[0] / 4;A[0] %= 4;if （A[1]）{A[0] -= 2;nums++;}if （A[0] > 0） nums++;}cout<<nums;}

题目出处：

From：csdn博客靖心