Codeforce 839 B. Game of the Rows 解析(思維)

今天我們來看看CF839B
題目連結

題目
有如下圖片所示的飛機座位$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