1575. Spring Tour

Description

中文English

There are n group children ready to go on a spring tour. The array a indicates the number of people in each group. There are no more than four people in each group. There are now several cars. Each car can only take up to four people. The same group of children must sit in the same car, and each car need't be full. Ask how many cars you need to meet the travel needs of your children.

• $0 \leq n \leq 1e4$
• $1 \leq a[i] \leq 4$

Have you met this question in a real interview?  

Example

Example1

Input: a = [1,2,3,4]
Output: 3
Explanation: 
At this time, there are 4 people in the fourth group, sitting alone in a car.
The first group has 1 person, the third group has 3 people, and just 4 people get for one car.
The second group of 2 people has a single car, so at least 3 cars are needed.

Example2

Input: a = [1,2,2,2]
Output: 2
Explanation: 
The first group and the second group get one car
The third group and the fourth group get one car
Therefore, at least two cars are needed.

Code(Language:C++)

class Solution {
public:
    /**
     * @param a: The array a
     * @return: Return the minimum number of car
     */
    int getAnswer(vector<int> &a) {
        // Write your code here
        const int size = a.size();
        if(size == 0){
            return 0; 
        }
        vector<int> arr(4, 0); 
        for(int i = 0; i < size; i++){
            arr[a[i] - 1]++; 
        }
        
        //1,2,3,4 (1,1)(1,2) (1,3) ()
        // 1, 2, 3 
        int cnt = arr[3]; 
        if(arr[2] >= arr[0]){
            cnt += arr[2]; 
            cnt += (arr[1] + 1) / 2; 
        }
        else{
            cnt += arr[2]; 
            arr[0] -= arr[2]; 
            if(arr[0] >= 2 * arr[1]){
                cnt += arr[1];
                arr[0] -= 2 * arr[1]; 
                cnt += (arr[0] + 3) / 4; 
            }
            else{
                cnt += (arr[0] + 1) / 2; 
                arr[1] -= (arr[0] + 1) / 2; 
                cnt += (arr[1] + 1) / 2; 
            }
        }
        return cnt; 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41