---
title: Codeforce 839 B. Game of the Rows 解析(思維)
description: "Codeforce 839 B. Game of the Rows 解析(思維)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 839 B. Game of the Rows 解析(思維)">
<!-- toc -->

# Codeforce 839 B. Game of the Rows 解析(思維)
今天我們來看看CF839B
[題目連結](https://codeforces.com/problemset/problem/839/B)

> **題目**
有如下圖片所示的飛機座位$n$排，和$k$隊士兵，每隊數量不一定。
求是否可以每隊都坐上去並且沒有任何兩個士兵相鄰「並且」是不同隊的。

### 前言
思考時小心一點，記得座位有很多種捨棄方法

### 想法
注意到，在座位足夠的情況下，我們可以有三步驟的方法來捨去座位。
1. 把中間的$4$個座位分成$1,2$人座位 (此步把可以得到的間隔都得到了)
2. 把左右的2個2人座位隨便選一個(或者兩個都選)捨去一個座位，變成$1$人座位
3. 把中間已經拆成$1,2$人座位的4個座位，再捨去一個，變成$1,1$人座位

($2.3.$兩個步驟是在把$2$人座位換成$1$人座位，這樣才能方便等等的分配座位順利運行)
接著要把士兵一隊一隊分配進去。現在已經有$1,2,4$人座位的數量了，而這些座位都是分開的，那麼我們只要從最大的座位開始把士兵分配進去就好。

### 程式碼:

const int _n=1e4+10;
int t,tt,ttt,n,k,a[_n],sum=0,cnt[5];
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);
  cin>>n>>k;rep(i,0,k){cin>>a[i];sum+=a[i];} cnt[2]=2*n,cnt[4]=n;
  t=min(n,8*n-sum); cnt[1]=t,cnt[2]+=t,cnt[4]-=t;
  if(t==n){tt=min(2*n,8*n-n-sum); cnt[1]+=tt,cnt[2]-=tt;}
  if(tt==2*n){ttt=min(n,8*n-n-n-n-sum); cnt[1]+=ttt,cnt[2]-=ttt;}
  rep(i,0,k){
    int f=min(cnt[4],a[i]/4);
    cnt[4]-=f; a[i]-=4*f;
    f=min(cnt[2],a[i]/2);
    cnt[2]-=f; a[i]-=2*f;
    f=min(cnt[1],a[i]);
    cnt[1]-=f; a[i]-=f;
    if(a[i]){cout<<"NO\n";return 0;}
  }cout<<"YES\n";
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/839/submission/90458994)