Google code jam 2010 Round 1C A.Rope Intranet

問題概要

左側のビルと右側のビルにN本のロープが結ばれている。
それぞれのロープは左側のビルのAi階の窓と右側のBi階の窓に結ばれているものとする。

このとき、（建物を横から見たときの）ロープの交差の数を数えよ。
ただし3本以上のロープが一点で交差したり、一つのビルの一つの階に2本以上のロープが結ばれているようなことはないとする。
各数の範囲は
1≦A,B≦10^4,
1≦N≦1000である。

解法

あみだくじのスタートとゴールが与えられたときに引く横線の数を求める問題と同じである。
Ai,BiとAj,Bjのロープが交点を持つことは、Ai,AjとBi,Bjの大小関係が逆転していることに一対一に対応する（言葉ではわかりにくいけど図をかけばすぐに言っていることがわかると思うｗ）

よって、右側の階の数列を、対応する左側の数列の順にソートした後での転置（逆転）の数を数えればよい。

Nは1000以下と小さいので以下のO(N^2)の解法で一瞬で終わる。

ソースコード

pi pr[1000];

int main()
{
	int CS; cin>>CS;
	rep(cs,CS)
	{
		int n; cin>>n;
		
		int a,b;
		rep(i,n)cin>>a>>b,pr[i]=mp(a,b);
		sort(pr,pr+n);
		
		int ans=0;
		rep(i,n)rep(j,i)if(pr[i].second<pr[j].second)ans++;
		
		cout<<"Case #"<<cs+1<<": "<<ans<<endl;
	}
	
	return 0;
}