読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #274, Division 1, A ( Division 2, C ) : Exams

問題概要

 ある学生は n 科目の試験を受ける。i 番の科目の試験は、本来ならば試験期間の a_i 日目に実施されるが、教官との交渉により b_i ( < a_i ) 日目に受験することも認められた。i 番の科目の試験を受けたとき、教官は学生の記録簿に本来の試験日である a_i を追記する。同日に受けられる試験の数に制限は無い。
 学生はできるだけ早く全ての試験を受け終えたいが、記録簿に記載された日付が広義単調増加になっていなければ不自然である。そこで、記録簿に記載される日付が広義単調増加となるように試験を受けることにした。このとき、最短で何日目に全ての試験を受け終わるか求めよ。

解法

 題意より、受験する順序に a_i の値を並べた列は広義単調増加になっていなければなりません。また、可能であれば b_i 日目に試験を受けた方が全科目を受け終わるのが早くなります。
 従ってまずは各受験日の情報をタプルにして a_i をキーに昇順ソートし、この順に処理します。ある時点で d 日目になっているとすると(初期状態では d = 0 )、d \leq b_i となっている科目は b_i 日目に、そうでない科目は a_i 日目に受験することで、記録簿の状態を valid に保つことができます。完了の早い順に処理しているので、最適解が得られます*1

コード

using PII = pair<int,int>; using VPII = vector< pair<int,int> >;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define fst first
#define snd second

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VPII ab( n );
	REP( i, 0, n )
	{
		cin >> ab[i].fst >> ab[i].snd;
	}
	sort( ALL( ab ) );

	int d = 0;
	FOR( p, ab )
	{
		d = d <= p.snd ? p.snd : p.fst;
	}

	cout << d << endl;

	return 0;
}

*1:ちゃんと示してませんが、区間幅が全て 1 の区間スケジューリングみたいな