AtCoder ABC 382 C - Kaiten Sushi

公式の解説などに「二分探索」があり、もしかしてまた偽ACをやってしまったのか・・？ と不安になって再整理したので、せっかくだから晒しておきます。

コンテスト中に考えたこと

• 人数(N)と寿司(M)が 2 x 10^5 なので総当たりしたら間に合わないよねぇ
• 寿司はどの順で流しても誰に食べられるのかの結果は変わらないから、好きな順で判定しても大丈夫
• ということは、寿司をおいしい順に並べて、最初の客が食うものを記録して次の評価から除外、残りを次の客が食べるか、を順に判定していけば、線形に何回か回るだけでいけるか
• 「プラットフォーム」みたいだな。（思考のノイズ）

結果

Main.cpp

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

struct Sushi {
	ll number;	// 皿番号
	ll star;	// おいしさ
	ll eater = -1;	// 食べた人

	// priority_queue に「おいしさ」順に並べてもらうための演算
	bool operator<( const Sushi & other ) const
	{
		return star < other.star;
	}

	bool operator>( const Sushi & other ) const
	{
		return star > other.star;
	}
};


int main( void )
{
	// 入力
	ll N, M;
	cin >> N >> M;

	vector<ll> vecA(N+1);
	for( ll i = 1; i <= N; ++i)
	{
		cin >> vecA[i];
	}

	// 寿司がおいしい順に並んでいるキューを作成
	priority_queue<Sushi> pq;
	for( ll i = 1; i <= M; ++i)
	{
		ll _star;
		cin >> _star;
		Sushi tmp = { i, _star, -1 };
		pq.push( tmp );
	}

	// 結果格納用
	vector<Sushi> vecResult;
	// 上流に並んでいる客が食べてしまう皿を順に選別していく
	for( ll i = 1; i <= N; ++i)
	{
		while( ! pq.empty() )
		{
			Sushi _sushi = pq.top();
			if( vecA[i] <= _sushi.star )
			{
				// 食べる客を更新して結果に追加
				_sushi.eater = i;
				vecResult.push_back( _sushi);
				// キューからは消す
				pq.pop();
			}
			else
			{
				break;
			}
		}
	}
	// 誰も食べなかった皿も追加
	while( ! pq.empty())
	{
		Sushi _sushi = pq.top();
		vecResult.push_back( _sushi);
		pq.pop();
	}

	// 結果を皿番号順に並べなおして出力
	sort( vecResult.begin(), vecResult.end(), [](const Sushi & a, const Sushi & b){ return a.number < b.number;} );
	for( auto itr = vecResult.begin(); itr != vecResult.end(); ++itr)
	{
		cout << itr->eater << endl;
	}

	return 0;
}