创想实验室
我们都是梦想家

Team Travel

描述

There are many tourism attractions in Hangzhou, and today n groups of people are taking a tour of Hangzhou on the same bus. There are ai persons in the i-th group.

There are m two-seat blocks and p four-seat blocks in this bus. As the name suggests, there are two seats next to each other in a two-seat block, and there are four seats in a row in a four-seat block. For safety reasons, no one should sit adjacent to a person from another group. Two seats are considered adjacent if and only if they belong to the same block and their positions in the block are adjacent. In other words, the two seats in a two-seat block are adjacent. For a four-seat block, if we denote the seats in a four-seat block from left to right A,B,C,D respectively (see the gure below), then the pairs (A,B) and (B,C) and (C,D) are adjacent.

Please determine if it is possible to arrange seating for those n groups without violating the restrictions above.

输入

The first line of the input contains a single integer T (1 ≤ T ≤ 100), the number of test cases. T cases follow.

The first line of each test case contains three integers m,p,n, denoting the number of two-seat blocks, the number of four-seating blocks and the number of groups, respectively.

The second line contains n integers, the i-th integer denotes ai, the number of persons in the i-th group. It is guaranteed that: 0 ≤ m ≤ 10000, 1 ≤ n ≤ 100, 0 ≤ p ≤ 5000, 1 ≤ ai ≤ 10000.

输出

For each test case, output in a single line YES (without quotes) if a valid seating arrangement exists, otherwise output NO (without quotes).

样例输入

样例输出

题解

这题是一题比较大的贪心模拟题,第一步是把所有大于3的队伍变成小于3的,优先级是4>2,第二步是把等于2的队伍变成小于2的,优先级2>4>1(这个要好好想想),最后就是统计剩余座位个数s1+s2+s4*2和队伍个数比较。因为涉及到排序,所以用了优先队列。

代码

 

网站所发布的代码已提交通过,代码可能经过修改防止抄袭,未经允许不得转载:创想实验室 » Team Travel
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址