Taxi"/>
158B.Taxi
158B.Taxi
- 题目
- 翻译
- 题目
- 输入
- 输出
- 分析
- 代码
题目
翻译
题目
放学后有个 n n n组小学生打算去Polycarpus去庆祝生日。已知第 n n n组有 s s si个小朋友( 1 ≤ 1 ≤ 1≤ s s si ≤ 4 ≤4 ≤4)并且他们想一起去Polycarpus。他们决定乘出租去。每辆车最多可以搭乘4名乘客。如果每组小学生均需乘坐在同一辆车上,那最少需要多少辆车?(一辆车可以搭乘多组小学生)
输入
第一行为整数 n n n( 1 ≤ n ≤ 10 1 ≤ n ≤ 10 1≤n≤105) 一 组数。第二行为一序列 s s s1, s s s2,…, s s sn( 1 ≤ 1 ≤ 1≤ s s si ≤ 4 ≤4 ≤4).整数由空格分隔开, s s si表示第 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;
}
更多推荐
158B.Taxi
发布评论