18146: 乌鸦坐飞机

implementation, http://cs101.openjudge.cn/practice/18146

黑虎阿福有 k 窝乌鸦，他想要让这些乌鸦坐飞机。黑虎阿福拥有 n 架飞机，每架飞机上的座位排布都是相同的，如下所示： 1 2 | 3 4 5 6 | 7 8 即1-2、3-4、4-5、5-6、7-8号座位是相邻的。所有的乌鸦都要求：与自己的座位相邻的座位上，不能有不来自同一窝的乌鸦坐在上面。试判断黑虎阿福能否成功地让这些乌鸦坐飞机。

输入

第一行有2个整数，n 和 k ( 1 ≤ n ≤ 10000, 1 ≤ k ≤ 100 ) ，分别为飞机数和乌鸦的窝数；第二行有 k 个整数 a1、a2、……、ak ( 1 ≤ ai ≤ 10000 ) ，其中 ai 是第 i 窝乌鸦的只数。

输出

如果这些乌鸦能符合要求地坐飞机，输出YES；如果不能，输出NO。

样例输入

Sample Input1：
1 2
4 4

Sample Output1:
YES

样例输出

Sample Input2：
1 2
1 7

Sample Output2:
NO

来源：cs101-2018 邱子龙

python

# 蒋子轩23工学院
n, _ = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0]*4
for i in a:
    cnt[i % 4] += 1
# add为空位数
add = cnt[1]+cnt[3]  # 余1或3的必定会造成一个空位
# 余2的优先放1、2和7、8，或和余1的组合放中间，不会增加空位数
t = cnt[2]-2*n-cnt[1]
if t > 0:  # 若还有余2的没能放好
    # 分类讨论余2的至少造成多少个空位
    add += t//3*2
    if t % 3 == 1:
        add += 2
    if t % 3 == 2:
        add += 4
print('YES' if sum(a)+add <= n*8 else 'NO')

python

n, k = map(int, input().split())
inp = list(map(int, input().split()))

# print('inp = ', inp)

a = n*2  # 12 / 78 这种两个连着的位置的数目，易知12必须来自同一窝，78也必须来自同一窝
b = n  # 3456 Z这种4个连着的位置的数目，易知3456必须来自同一窝

# 考虑到相邻的位置要坐来自同一窝的乌鸦，首先分配4连座
# b代表剩余未分配的4连座数目
for i in range(k):
    x = inp[i]//4  # x代表第i窝乌鸦的数目是4的多少倍
    y = min(x,b)  # y代表第i窝乌鸦还能分配出去的4连座数目
    b -= y  # b代表把第i窝分配到4连座之后，还剩下未分配的4连座数目
    inp[i] -= (y*4)  # 第i窝乌鸦的数目减掉已分配4连座的乌鸦数目
    if b==0: break
    
# 由于4连座不能拆成两个2连座，先当成一个2连座
# a是剩余未分配的2连座数目
a += b
for i in range(k):
    x = inp[i]//2  # x代表第i窝乌鸦的中未分配的数目是2的多少倍
    y = min(x,a)  # y代表第i窝乌鸦还能分配出去的2连座数目
    a -= y  # a代表把第i窝分配到2连座之后，还剩下未分配的2连座数目
    inp[i] -= (y*2) # 第i窝乌鸦的数目减掉已分配2连座的乌鸦数目
    if a==0: break
    
# sum(inp)是剩余未分配的乌鸦总数，若能分配开应该是0
# b是剩余的4连座，由于之前把b当成2连座加入a分配了，此时b剩下两个座位，但是只能坐一只来自不同窝的乌鸦
# a是剩余的2连座，只能坐一只来自不同窝的乌鸦
# a + b是剩余未分配的座位数，也就是能坐下的乌鸦数目，这里答案的写法只考虑了此时一只乌鸦分配到一个空的2连座或者一个已经有两个人的4连座上，所以是sum(inp) <= (a+b)
# 若飞机座位太少，可能每窝乌鸦都剩下好多只，必然有a = b = 0，此时也是不满足条件的
if sum(inp) <= (a+b):
    print ("YES")
else:
    print ("NO")

18146: 乌鸦坐飞机 ​

18146: 乌鸦坐飞机