AtCoder ARC #147 : C - Min Diff Sum

ちょっと出来の悪かった回。
https://atcoder.jp/contests/arc147/tasks/arc147_c

問題

N要素の整数列Xの不満度は、2要素の差の絶対値の総和とする。
L[i]≦X[i]≦R[i]でなければならないという区間[L[i],R[i]]がそれぞれ指定される。
不満度の最小値を求めよ。

解法

全要素ができるだけ近くに揃うようにした方が良い。
f(x)を、Xの各要素がxに近づくように取ったときの2要素の差の絶対値の総和とすると、f(x)は下に凸な関数となる。
よって三分探索していこう。

int N;
int L[303030],R[303030];

ll hoge(int m) {
	vector<ll> V;
	int i;
	FOR(i,N) {
		if(m<L[i]) V.push_back(L[i]);
		else if(m>R[i]) V.push_back(R[i]);
		else V.push_back(m);
	}
	sort(ALL(V));
	ll ret=0;
	FOR(i,N) {
		ret+=i*V[i]-(N-1-i)*V[i];
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> cand;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		cand.push_back(L[i]);
		cand.push_back(R[i]);
	}
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	
	ll mi=1LL<<60;
	int TL=0,TR=cand.size()-1;
	mi=min(mi,hoge(TL));
	mi=min(mi,hoge(TR));
	while(TR-TL>=3) {
		int m1=(TL*2+TR)/3;
		int m2=(TR*2+TL)/3;
		ll v1=hoge(cand[m1]);
		ll v2=hoge(cand[m2]);
		mi=min(mi,v1);
		mi=min(mi,v2);
		if(v1<v2) TR=m2;
		else if(v1>v2) TL=m1;
		else TL=m1,TR=m2;
	}
	for(i=TL;i<=TR;i++) mi=min(mi,hoge(cand[i]));
	
	cout<<mi<<endl;
	
}

まとめ

これはそこまで苦労せず思いついてるな。