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

今天我們來看看CF839B

題目連結

題目

有如下圖片所示的飛機座位\(n\)排，和\(k\)隊士兵，每隊數量不一定。

求是否可以每隊都坐上去並且沒有任何兩個士兵相鄰「並且」是不同隊的。

前言

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

想法

注意到，在座位足夠的情況下，我們可以有三步驟的方法來捨去座位。

把中間的\(4\)個座位分成\(1,2\)人座位 (此步把可以得到的間隔都得到了)
把左右的2個2人座位隨便選一個(或者兩個都選)捨去一個座位，變成\(1\)人座位
把中間已經拆成\(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