Bubble Cup 8 Final : F. Bulbo

ややこしいけどコードは短い。
http://codeforces.com/contest/575/problem/F

問題

初期状態でプレイヤーは１次元座標軸の位置Xにいる。
N個の区間[L[i],R[i]]が与えられる。
プレイヤーはその都度各区間の中に含まれるよう移動しなければならない。
最小の総移動量を求めよ。

解法

各区間に入る時点の最小移動量と、その移動量でプレイヤーが要られる区間[l,r]を適宜更新していく。
今いる[l,r]に対し次の区間がその外側にあるなら、最寄りの位置から移動するようにしていくと良い。

int N,X;
ll L[5050],R[5050];

ll CL,CR;
ll tot;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	CL=CR=X;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		if(CR<=L[i]) {
			tot += L[i]-CR;
			CL=CR;
			CR=L[i];
		}
		else if(R[i]<=CL) {
			tot += CL-R[i];
			CR=CL;
			CL=R[i];
		}
		else {
			CL=max(CL,L[i]);
			CR=min(CR,R[i]);
		}
	}
	cout<<tot<<endl;
}

まとめ

シンプルだけど良い問題。