[Codeforces] 839B. Game of the Rows

題目連結:http://codeforces.com/problemset/problem/839/B

---

第一次會想把Div2的pB拿來放在這XD，這題實在有夠難寫的雖然一眼就知道他是greedy，但是思路要是不夠清楚基本上就會爛掉(這場CF我就這題炸掉了QAQ....)。Greedy的想法還算簡單，只要讓人數多的集團先坐，而且優先先把四人座坐滿即可(因為四人座若要做兩組人，中間一定會少一格(不能當作2格跟2格)，接下來再做兩人座的部分。這時可能會剩一些座位空著就在想盡辦法把所有人都塞進，這裡一樣先把多的人塞到4人座裡面。

#include <bits/stdc++.h>
using namespace std;

int seat[5], arr[10000 + 5];

int main(){
	int n, k; cin>>n>>k;
	seat[4]=n;
	seat[2]=2*n;
	for(int i=0;i<k;i++) cin>>arr[i];
	sort(arr, arr+k, [](int a, int b){return a>b;});
	for(int i=0;i<k;i++){
		int qq = min(arr[i]/4, seat[4]);
		arr[i] -= qq*4;
		seat[4]-=qq;
	}
	sort(arr, arr+k, [](int a, int b){return a>b;});
	for(int i=0;i<k;i++){
		int qq = min(arr[i]/2, seat[2]);
		arr[i] -= qq*2;
		seat[2]-=qq;
	}
	priority_queue<int> pq;
	for(int i=0;i<k;i++) pq.push(arr[i]);
	while(!pq.empty()){
		if(pq.top()<=0) break;
		if(seat[4] > 0){
			int x = pq.top(); pq.pop();
			seat[4]--;
			if(x==2) seat[1]++;
			else if(x==1) seat[2]++;
			x -= min(x, 4);
			if(x>0) pq.push(x);
		}else if(seat[2] > 0){
			int x = pq.top(); pq.pop();
			seat[2]--;
			x -= min(x, 2);
			if(x>0) pq.push(x);
		}else if(seat[1] > 0){
			int x = pq.top(); pq.pop();
			seat[1]--;
			x -= min(x, 1);
			if(x>0) pq.push(x);
		}else{
			break;
		}
	}
	cout<<((pq.empty() or pq.top()<=0)?"YES\n":"NO\n");
	return 0;
}

C++