158B.Taxi

Taxi"/>

158B.Taxi

158B.Taxi

• 题目
• 翻译
• • 题目
  • 输入
  • 输出
• 分析
• 代码

题目

翻译

题目

    放学后有个 n n n组小学生打算去Polycarpus去庆祝生日。已知第 n n n组有 s s s_i个小朋友( 1 ≤ 1 ≤ 1≤ s s s_i ≤ 4 ≤4 ≤4)并且他们想一起去Polycarpus。他们决定乘出租去。每辆车最多可以搭乘4名乘客。如果每组小学生均需乘坐在同一辆车上，那最少需要多少辆车？（一辆车可以搭乘多组小学生）

输入

    第一行为整数 n n n（ 1 ≤ n ≤ 10 1 ≤ n ≤ 10 1≤n≤10⁵) 一 组数。第二行为一序列 s s s₁, s s s₂,…， s s s_n( 1 ≤ 1 ≤ 1≤ s s s_i ≤ 4 ≤4 ≤4).整数由空格分隔开， s s s_i表示第 i i i组中孩子的数量.

输出

    输出一个数 一 最小的出租车数

分析

    分析题意可知，人数达4或3的小组需分配一辆车，其中人数为1的小组可以和人数为3的小组搭一辆车，人数为2的小组先与人数为2的小组同搭，如果有多出来的再和人数1的同搭，最后处理人数为1的小组。

代码

#include<iostream>
using namespace std;
int main()
{int a[5] = { 0 };int n,number,num = 0;cin >> n;while (n--){cin >> number;a[number]++;}num += a[4] + a[3];//人数4和3的小组直接开新车num += a[2] / 2+ a[2] % 2;//先让人数为2的小组折半，然后看是否还有剩余，//剩余只可能为0或1个组a[1] = a[1] - a[3] > 0 ? a[1] - a[3] : 0;//看和3人数小组同搭后1人数小组剩余a[1] = a[2]%2!=0?( a[1] > 2 ? a[1] - 2:0 ):a[1];//先看2人数小组是否有剩余//再看1人数小组是否可以有剩余。num += a[1]/4+(a[1]%4==0?0:1);//按4组分，并且判断是否有剩余，剩余再开一辆车cout << num;return 0;
}