当前位置：首页 > article >正文

Codeforces 158B. Taxi

article 2025/3/17 9:02:09

题目

题目链接：https://codeforces.com/problemset/problem/158/B

time limit per test:3 seconds;memory limit per test:256 megabytes

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

Input

5
1 2 4 3 3

Output

Input

8
2 3 4 4 2 1 3 1

Output

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.

思路

贪心+ 双指针，先考虑简单的情况，给出此种情况下的粗略算法，再考虑复杂的情况，升级算法。先对小组的人数进行排序。简单的情况就是判断对于首尾两个指针，相应的小组人数是否小于等于4 ，满足条件则计数加1 。当然，这是有缺陷的，因为像 1 1 1 1,1 1 1 2 3 这样的数据，就不能得到正确的答案了。因为只有两个指针，所以可以将接着判断如果加上下一个小组的人数，总的小组人数是否满足条件，根据情况做出移动指针的操作。代码中条件语句出现的顺序也很重要。

代码

n=int(input())
s_list=list(map(int,input().split()))
# print(s_list)
s_list.sort()
# print(s_list)
t=0
i,j=0,n-1
while i<=j:
    if i==j and s_list[i]<=4:
        t+=1
        i+=1
        j-=1
        # print(i-1,j+1,s_list[i-1])
    elif s_list[i]+s_list[j]<=4:
        group_sum=s_list[i]+s_list[j]
        if group_sum+s_list[i+1]<=4 and i!=j-1:
            s_list[i+1]=s_list[i]+s_list[i+1]
            i += 1
        else:
            t+=1
            i+=1
            j-=1
            # print(i-1,j+1,s_list[i-1]+s_list[j+1])
    elif s_list[j]<=4:
        t+=1
        j-=1
        # print(i,j+1,s_list[j+1])
    elif s_list[i]<=4:
        t+=1
        i+=1
        # print(i-1,j,s_list[i-1])
print(t)

查看全文

http://www.kler.cn/a/588142.html