[BOJ 3163]完全探索2-落下アリ

最初は完全に探索で解決しようとした.
N個のアリに対して最大L回回転し、タイムアウトするしかない.
これは実現よりも考え方が難しい問題だ.

アイデア

衝突が発生しても、最終的に下がる時間は同じです.
着替えと完成した枝までまっすぐ行きます.

衝突時-方向と+方向の合計は固定されます.

落ちてもどうせ端から落ちなければならない.

この図を例にとる.
+プラス3個-プラス3個で、結果は0に近い3個のアリ、-乙Lに近い3個のアリは+があります.
つまり、+4+5-1は0、-1-3-2は30

じつかい

アリを目的距離で入力します.

a < 0 ? ant.push_back({ p, a }) : ant.push_back({ L - p, a });

入力したアリを距離をソートします.

sort(ant.begin(), ant.end());

まず落としたアリから始め、負数IDを持つアリであれば、0に近いアリが落ちます.
逆にLに近いアリを撃ち落とす.

if (i != N-1 && ant[i].first==ant[i+1].first) // 같이떨어지는경우
{
	if (frontValue < backValue) { // id작은게 먼저 떨어짐
		answer.push_back(frontValue);
		answer.push_back(backValue);
	}
	else {
		answer.push_back(backValue);
		answer.push_back(frontValue);
	}
	i++;
	idList.pop_front();
	idList.pop_back();
}
else if (ant[i].second < 0) {
	answer.push_back(frontValue);
	idList.pop_front();
}
else {
	answer.push_back(backValue);
	idList.pop_back();
}