CentipedeSocks [SRM757 Div1 Easy]

C匹のムカデがいる。
各ムカデはF本の足がある。
あるムカデには同じ色の靴下を履かせたい。

N種類の靴下があり、それぞれ数がわかっている。
全て1つの瓶に入っていて、ランダムに取り出していく。
全てのムカデに同色の靴下を履かせるときに、取り出す靴下の最大数は？
全部取り出しても履かせられないなら-1

解説

貪欲法で解く。
まず、F本に満たない種類の靴下は全て先に出しておこう。
F本以上の種類の靴下はF-1本取り出しておく。
これで、どのムカデも完成していない状態で最大数取り出せる本数を取り出した。
ここから、残っている本数が多い順に靴下を取っていく。
基本はF本一気に取り出すことで、1種類完成させて、F-1本ギリギリの状態で残すことを繰り返す。
F本に満たない場合は、しょうがないので全部取り出して、その種類の靴下はもう使わないことにする。
最後のムカデはF-1本ギリギリの状態で残すことはできないので、+1をして答える。
これを繰り返して、C匹のムカデを用意できないなら-1

struct CentipedeSocks {
	int fewestSocks(int C, int F, vector <int> socks) {
		priority_queue<int> que;
		int ans = 0;
		fore(x, socks) {
			if (x < F) ans += x;
			else {
				ans += F - 1;
				que.push(x - (F - 1));
			}
		}

		while (0 < C and !que.empty()) {
			int q = que.top(); que.pop();

			if (C == 1) {
				ans++;
				return ans;
			}

			C--;
			
			if (F < q) que.push(q - F);
			ans += min(F, q);
		}

		return -1;
	}
};