題意
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CN2UTOxQzMwYTMtETN4cDMyIDNwMTM4AzNxAjMtQTO0kzN48CX4AzNxAjMvwFN5QTO3gzLcd2bsJ2Lc12bj5ycn9Gbi52YucTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
飛機有n排如圖座位,給出k個部落和各部落人數ai,問能否安排使得所有人入座且不同部落的人都不會緊鄰。資料保證總人數不超過總座位數。
分析
首先考慮所有4個人同部落的組合,優先安排在中間的四座上,如果四座坐滿,再安排在二坐上。此時剩下的人不會有(超過)四個人來自同一部落。
然後考慮所有2個人同部落的組合,優先安排在兩邊的二坐上,如果二坐坐滿,再安排在四座上。此時剩下的人不會有(超過)兩個人來自同一部落,即剩下的t個人都來自不同部落。
考慮三個人坐四座,AA_A還是AAA_,兩種情況都不能再坐進其他部落的人,不妨騰出一個單座供剩下的人坐成AA_B(也即第三個A看作剩下的人)。
設四座數量為a,二座數量為b,三座數量為c,此時還能坐下a*2+b+c個不同部落的人。若t<=a*2+b+c則剩下的人都有位置坐,否則沒有符合的方案。
代碼
int n,k,t[10007],tot;
bool ac(){
int a=n,b=n*2,c=0;
for(int i=1;i<=k&&a;i++){
tot-=t[i];
if(t[i]/4>a){
t[i]-=a*4;a=0;
}
else{
a-=t[i]/4;t[i]%=4;
}
tot+=t[i];
if(tot==0)return true;
}
for(int i=1;i<=k&&b;i++){
tot-=t[i];
if(t[i]/2>b){
t[i]-=b*2;b=0;
}
else{
b-=t[i]/2;t[i]%=2;
}
tot+=t[i];
if(tot==0)return true;
}
for(int i=1;i<=k&&a;i++){
tot-=t[i];
if(t[i]/2>a){
t[i]-=a*2;c+=a;a=0;
}
else{
a-=t[i]/2;c+=t[i]/2;t[i]%=2;
}
tot+=t[i];
if(tot==0)return true;
}
return tot<=a*2+b+c;
}
int main(){
scanf("%d%d",&n,&k);
tot=0;
for(int i=1;i<=k;i++){
scanf("%d",&t[i]);tot+=t[i];
}
printf(ac()?"YES\n":"NO\n");
return 0;
}
轉載于:https://www.cnblogs.com/shuiming/p/7352267.html