车辆安排

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K

链接：https://www.nowcoder.com/acm/contest/112/B
来源：牛客网

题目描述

有n个队伍，每个队伍的人数小于等于5，每辆车最多坐5个人，要求一个队伍的人都在一辆车上，求最少的车数

输入描述:

第一行n
第二行n个数，表示每个队伍的人数

输出描述:

输出最少车数

示例1

输入

3
3 4 5

输出

3

备注:

n≤1e5
每个数小于等于5

解题报告

题意：这道题相当于，给你体积为5的包，让你去装n个体积不超过5的物品（不可分割），求所用包的最少数量。

解题思路：先把体积为5的装上，然后体积为4的和体积为1的、体积为3的和体积为2的可以一块装，两个体积为1的和一个体积为3的、三个体积为1的和一个体积为2的、两个体积为2的和一个体积为1的也可以放在一起装。其中，如果体积为4的多余体积为1的，显然剩余的体积为4的就是一个装一个。具体的见代码：

#include <stdio.h>
#include <string.h>
int main()
{
	int n, m, ans, s[10];
	while (~scanf("%d", &n))
	{
		ans = 0;
		memset(s, 0, sizeof(s));
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &m);
			s[m]++;
		}
		ans += s[5];
		s[5] = 0;
		while (s[4])
		{
			ans++;
			s[4]--;
			s[1]--;
			if (s[1] < 0)
				s[1] = 0;
		}
		while (s[2] && s[3])
		{
			s[3]--;
			s[2]--;
			ans++;
		}
		while (s[2])
		{
			ans++;
			if (s[2] == 1)
			{
				s[2]--;
				s[1] -= 3;
				if (s[1] < 0)
					s[1] = 0;
			}
			else
			{
				s[1]--;
				s[2] -= 2;
				if (s[1] < 0)
					s[1] = 0;
			}
		}
		while (s[3])
		{
			ans++;
			s[3]--;
			s[1] -= 2;
			if (s[1] < 0)
				s[1] = 0;
		}
		if (s[1])
			ans += (s[1] + 4 ) / 5;
		printf("%d\n", ans);
	}
	return 0;
}