codeforce 158B Taxi

今天忘了写力扣的困难题，做了 codeforce 临时顶一题，以后还是主要力扣哈。

Problem - 158B - Codeforces

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, ..., sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of children in the i-th group.

Output

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

Examples

5
1 2 4 3 3

output

4

input

8
2 3 4 4 2 1 3 1

output

5

Note

In the first test we can sort the children into four cars like this:

• the third group (consisting of four children),
• the fourth group (consisting of three children),
• the fifth group (consisting of three children),
• the first and the second group (consisting of one and two children, correspondingly).

There are other ways to sort the groups into four cars.

大概就是说，一组的人数是1到4人，出租车可以塞4个人。不同组的人可以凑在一辆出租车，同组的人不能分开，问至少需要几辆出租车。 

输入第一行：总组别数

输入第二行：每组人数

做题结果

成功

方法：贪心

想要出租车数目尽量少，那应该优先安排人多的先上车。

4个人的直接一组没有异议。

3个人可以和1个人凑成一队的就凑一块，不能只能3人一组

2个人可以和2个人凑成一队的就凑一块，否则能和1个人凑一队就凑一块，否则只能单出来两个人

1个人尽量组成4人组，多出来单独坐车

import java.util.*;
 
public class Main {
    public static  void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int c = Integer.parseInt(sc.nextLine());
        int[] items = new int[5];
        for(int i = 0; i < c; i++){
            items[sc.nextInt()]++;
        }
 
        int ans = 0;
        ans += items[4];//4人已经组好队
 
        //拼4人的
        //3+1
        int team = Math.min(items[1],items[3]);
        ans += team;
        items[3]-=team;
        items[1]-=team;
        //3
        ans += items[3];
 
        //处理2人队
        //拼4个人 2+2的先拼
        team = items[2]/2;
        ans += team;
        items[2]-=team*2;
 
        //2+1+1
        team = Math.min(items[1]/2,items[2]);
        ans += team;
        items[1]-=team*2;
        items[2]-=team;
 
        //2+1
        team = Math.min(items[1],items[2]);
        ans += team;
        items[2]-=team;
        items[1]-=team;
        //2
        ans += items[2];
 
        //1,4人一队向上取整
        if(items[1]>0){
            ans += (items[1]-1)/4+1;
        }
 
        System.out.println(ans);
    }
}

总结

难在英文，codeforce有时为了有趣会写很多废话，然后就很多词看不懂。