Codeforces #679 Div1 A. Perform Easily

Cまでは順調だったんだけど。
http://codeforces.com/contest/1434/problem/A

問題

6本の弦があるギターを考える。
このギターの音色は整数列Aで表され、i番目の弦のj番目のフレットを押さえると、A[i]+j番目の音が出る。

ここでN個の音が指定される。
各音を、任意の弦で弾くとき、抑えるべきフレットの最大値と最小値の差を最小化すると、その値はどうなるか。

解法

とりあえずAを昇順にしておき、全音色を最初の弦で鳴らすことを考える。
ここから、「最大のフレットを押さえるべき音色について、弦を1つずらす」ということを繰り返しながら、押さえるフレットの最大値と最小値の差を見ていこう。

vector<int> A,B;
int N;
int id[101010];
int cur[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,6) {
		cin>>x;
		A.push_back(x);
	}
	cin>>N;
	FOR(i,N) {
		cin>>x;
		B.push_back(x);
	}
	sort(ALL(A));
	sort(ALL(B));
	A.erase(unique(ALL(A)),A.end());
	B.erase(unique(ALL(B)),B.end());
	
	N=B.size();
	multiset<int> M;
	vector<pair<int,int>> cand;
	FOR(i,N) {
		cur[i]=B[i]-A[0];
		FOR(j,A.size()-1) cand.push_back({B[i]-A[j],i});
		M.insert(cur[i]);
	}
	int ret=*M.rbegin()-*M.begin();
	sort(ALL(cand));
	reverse(ALL(cand));
	FORR(c,cand) {
		x=c.second;
		M.erase(M.find(cur[x]));
		id[x]++;
		cur[x]=B[x]-A[id[x]];
		M.insert(cur[x]);
		ret=min(ret,*M.rbegin()-*M.begin());
	}
	cout<<ret<<endl;
	
}

まとめ

なんか題意を読み解くのに手間取った。