Codeforces #513 D. Social Circles

この時間はさすがに出られないですね…。
http://codeforces.com/contest/1060/problem/D

問題

円形のテーブルにN人が来る。
各人、自身の左側にL[i]個、右側にR[i]個空席があるような席に座りたい。
テーブルは何個あってもよく、かつ席順を任意に決められる場合、全員の希望を満たすには最小何個のイスがあればよいか。

解法

一瞬戸惑う問題。
右側に大きく空間が欲しい人の右に、左側に大きく空間が欲しい人が来るのが良い。
L[i]、R[i]をそれぞれソートし、max(L,R)の総和を取ればよい。
自分自身の横に自分が来る、みたいなケースも生じるが、テーブルは何個でもよく、テーブルに自分だけ座るケースも許容されるので問題ない。

int N;
int L[101010],R[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i]>>R[i];
	sort(L,L+N);
	sort(R,R+N);
	ll ret=N;
	FOR(i,N) ret+=max(L[i],R[i]);
	cout<<ret<<endl;
}

まとめ

テーブル１個縛りだったらどう解くのがいいんだろう。