【-87】839C.Journey[贪心]

题目大意

有一个飞机,有n排位置,每排有八个位置,如图

然后有k种士兵要坐飞机,不同种的士兵不能坐在相邻的位置。
{1,2}{3,4}{4,5}{5,6}{7,8}为相邻的位置

问所有的士兵能否都上飞机

输入格式

第一行,2个数,n和k (1≤n≤10000, 1≤k≤100)表示飞机上有n排位置,有k种士兵要坐飞机
第二行,k个数ai,ai表示第i种士兵的人数 (1≤ai≤10000),

输出格式

如果所有人可以上飞机,输出YES,否则输出NO

输入样例

2 2
5 8

输出样例

YES

题解

首先先从大到小排序(其实不需要),s2表示双人位的个数,s4表示四人位的个数
初始:s1=0,s2=n*2,s4=n
如果人数很多,优先做四人位,如果剩下的人数为3人(或者人数本来为3人),并且有四人位,那么就做四人位(因为3个人如果分成2个双人位做就浪费一个位置了)(举例:n=1,k=3,a1=3,a2=2,a3=2这个时候应该让三个人坐{3,4,5},然后2个人的坐在两边的双人位)
然后2人位没位置了/自己的人数<=1了(1的先不坐两人位)。
如果还有1个士兵没坐下,就做单人位(单人位怎么来的见下面)
如果还有人,那就看还有没有四人位如果有就做
如果是2个人坐四人位,则会增加一个单人位
(比如,3,4坐一种士兵,5空着,6再做一种士兵,这样同样合法)
如果是1个人坐四人位,则会增加一个双人位
然后还有人,就做2人位
还有人,就做单人位
噫,假设最后还剩一个人让他坐双人位而不是单人位后面来2人的怎么破。
额我好像还没举出这种例子
还有人,就输出NO了。
然后就可以模拟了

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
long long n,k,m;
long long s2,s4,s1;
long long a[110];
long long er=2;
bool cmp(int aa,int bb)
{
return aa>bb;
}
int main()
{
scanf("%d%d",&n,&k);
s2=n*2;
s4=n;
for (int i=1;i<=k;i++) scanf("%d",&a[i]);
sort(a+1,a+k+1,cmp);
//排序一下可以省很多情况
for (int i=1;i<=k;i++)
{
if (a[i]>=4) //四个人以上先做四人位
{
m=min(a[i]/4,s4);
s4-=m;
a[i]-=(m*4);
}
if (a[i]==3) //刚好三个人占一个四人位
{
if (s4>0)
{
s4-=1;
a[i]-=3;
}
}
if (a[i]>=2) //然后坐两人位(坐满
{
m=min((a[i])/2,s2);
s2-=m;
a[i]-=m*2;
}
if (a[i]>0) //如果还有人
{
if (s1>0&&a[i]==1) //一个人
{
while (s1>0&&a[i]>0) //单人位
{
a[i]--;
s1--;
}
}
if (a[i]==0) continue;
if (s4>0) //如果还有4个人的位置
{
if (a[i]==2)//2个人坐就加一个单人位
{
s4--;
s1++;
a[i]=0;
} else
if (a[i]==1)//一个人坐就加一个双人位
{
s4--;s2++;
a[i]--;
}
}
if (s2>0&&a[i]>0)//然后还有人就坐2人位
{
s2--;
m=min(a[i],er);
a[i]=a[i]-m;
}
if (a[i]>0&&s1>0)//还有人就坐单人位
{
while (a[i]&&s1)
{
s1--;
a[i]--;
}
}
if (a[i]<=0) continue;
printf("NO");
return 0;
}
}
printf("YES");
return 0;
}