简单总结题意:
有一个数组,数组中的数值不会大于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; }
题目出处:
http://codeforces.com/problemset/problem/158/B