Codeforces #623 Div1 A. Recommendations

D問題の位置がおかしすぎた回。
https://codeforces.com/contest/1314/problem/A

問題

整数列T[i]が与えられる。
T[i]は、コストA[i]を払えばインクリメントできる。
Tの各要素をuniqueにするための最小総コストを求めよ。

解法

同じ値を持つものが複数ある場合、コストが高いものを残しそれ以外をインクリメントするのが良い。
そこで登場する値を小さい順に見て行きつつ、同着になっているについてはpriority_queueを使いコストが低い順に残すようにしていこう。

int N;
int A[202020],T[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	map<int,vector<int>> M;
	FOR(i,N) {
		cin>>T[i];
		M[A[i]].push_back(T[i]);
	}
	
	priority_queue<int> P;
	ll ret=0;
	ll sum=0;
	int pre=-1000000;
	FORR(m,M) {
		while(pre<m.first && P.size()) {
			sum-=P.top();
			ret+=sum;
			P.pop();
			pre++;
		}
		pre=m.first;
		FORR(a,m.second) {
			P.push(a);
			sum+=a;
		}
	}
	
	while(P.size()) {
		sum-=P.top();
		ret+=sum;
		P.pop();
	}
	cout<<ret<<endl;
}

まとめ

なんか問題文読みにくいと思ったらこれC問題で謎の絵が出てくる回か…。