首页 > 代码库 > Codeforces839B-贪心

Codeforces839B-贪心

2024-11-26 13:45:02   204人阅读

题意

技术分享

 

飞机有n排如图座位，给出k个部落和各部落人数ai，问能否安排使得所有人入座且不同部落的人都不会紧邻。数据保证总人数不超过总座位数。

分析

首先考虑所有4个人同部落的组合，优先安排在中间的四座上，如果四座坐满，再安排在二坐上。此时剩下的人不会有（超过）四个人来自同一部落。

然后考虑所有2个人同部落的组合，优先安排在两边的二坐上，如果二坐坐满，再安排在四座上。此时剩下的人不会有（超过）两个人来自同一部落，即剩下的t个人都来自不同部落。

考虑三个人坐四座，AA_A还是AAA_，两种情况都不能再坐进其他部落的人，不妨腾出一个单座供剩下的人坐成AA_B（也即第三个A看作剩下的人）。

设四座数量为a，二座数量为b，三座数量为c，此时还能坐下a*2+b+c个不同部落的人。若t<=a*2+b+c则剩下的人都有位置坐，否则没有符合的方案。

代码

 1 int n,k,t[10007],tot;
 2 bool ac(){
 3     int a=n,b=n*2,c=0;
 4     for(int i=1;i<=k&&a;i++){
 5         tot-=t[i];
 6         if(t[i]/4>a){
 7             t[i]-=a*4;a=0;
 8         }
 9         else{
10             a-=t[i]/4;t[i]%=4;
11         }
12         tot+=t[i];
13         if(tot==0)return true;
14     }
15     for(int i=1;i<=k&&b;i++){
16         tot-=t[i];
17         if(t[i]/2>b){
18             t[i]-=b*2;b=0;
19         }
20         else{
21             b-=t[i]/2;t[i]%=2;
22         }
23         tot+=t[i];
24         if(tot==0)return true;
25     }
26     
27     for(int i=1;i<=k&&a;i++){
28         tot-=t[i];
29         if(t[i]/2>a){
30             t[i]-=a*2;c+=a;a=0;
31         }
32         else{
33             a-=t[i]/2;c+=t[i]/2;t[i]%=2;
34         }
35         tot+=t[i];
36         if(tot==0)return true;
37     }
38     return tot<=a*2+b+c;
39 }
40 int main(){
41     scanf("%d%d",&n,&k);
42     tot=0;
43     for(int i=1;i<=k;i++){
44         scanf("%d",&t[i]);tot+=t[i];
45     }
46     printf(ac()?"YES\n":"NO\n");
47     return 0;
48 }

 

Codeforces839B-贪心


联系
我们