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; }
まとめ
なんか題意を読み解くのに手間取った。