yukicoder : No.2304 Distinct Elements

苦手なタイプの問題。
https://yukicoder.me/problems/no/2304

問題

整数列Aが与えられる。
要素を1つ選び、インクリメントまたはデクリメントできるものとする。
Aの各要素をdistinctとしたい。最小何回処理を行えばよいか。

解法

Aを昇順にしておき、B[i]=A[i]-iで置き換えよう。
やりたいのはB[i]≦B[i+1]とすることである。
B[i]＞B[i+1]の場合、わざわざB[i]＜B[i+1]にする必要はなく、B[i]=B[i+1]とすればよい。

典型テクとして、整数列においてインクリメント/デクリメントを繰り返して全要素を一致させる場合、中央値に合わせると処理回数が最小化できる。
これをもとに、Bを複数の数列に分割し、(同じ値にすべき区間とその中央値)の列としてあらわすことを考える。
この時、この中央値は単調増加でなければならない。

Stackの要領で、中央値が降順になっている箇所があれば、マージして中央値をそろえる、という手順を繰り替えそう。

int N;
int A[202020];
multiset<int> L[202020],R[202020];

int getML(int a) {
	return *L[a].rbegin();
}
int getMR(int a) {
	if(L[a].size()==R[a].size()) return *R[a].begin();
	return *L[a].rbegin();
}

void add(int t,int a) {
	L[t].insert(a);
	int x=*L[t].rbegin();
	L[t].erase(L[t].find(x));
	R[t].insert(x);
	if(R[t].size()>L[t].size()) {
		x=*R[t].begin();
		L[t].insert(x);
		R[t].erase(R[t].find(x));
	}
}

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	vector<int> s;
	FOR(i,N) {
		add(i,A[i]-i);
		s.push_back(i);
		while(s.size()>=2) {
			x=s.back();
			s.pop_back();
			y=s.back();
			s.pop_back();
			if(getML(y)<getMR(x)) {
				s.push_back(y);
				s.push_back(x);
				break;
			}
			if(L[x].size()<L[y].size()) swap(x,y);
			FORR(a,L[y]) add(x,a);
			FORR(a,R[y]) add(x,a);
			s.push_back(x);
		}
	}
	ll ret=0;
	FORR(a,s) {
		ll b=getML(a);
		
		FORR(v,L[a]) ret+=abs(b-v);
		FORR(v,R[a]) ret+=abs(b-v);
	}
	cout<<ret<<endl;
	
}

まとめ

聞いてしまえばすんなりなのだけど。