CF 990-D. Move Back at a Cost

思路讲解

我看题解说，注意到，每个块最多被move back一次，那为什么最多被移动一次那？

我个人的理解是因为我们是可以随意选择move back的顺序，所以我们可以让我们的move back自动搞为一个单调的。

其实这个题解主要还是坚定了我的信心，让我知道我做法的时间复杂度是没问题的，我前面想复杂了。

总体上的思路是用数据结构优化模拟法，当然发现加粗（每个块最多被move back一次）是非常重要的，否则很容易想复杂。

核心是这段程序

while (!pq.empty()) {
	pll temp=pq.top();
	pq.pop();
	if(temp.second>needBack){
		// 我们发现这个不要后移，那就不后移
		Ans[++idx]=temp.first;
		needBack=temp.second;
	}else{
		// 如果我们发现这个要后移，那我们就模拟后移
		pq.push({temp.first+1,N+back});
		back+=1;
	}
}

AC代码

https://codeforces.com/contest/2047/submission/300222017

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

typedef long long ll;
typedef std::pair<ll,ll> pll;
const ll MAXN=static_cast<ll>(1e5)+10;
ll N,T,A[MAXN],Ans[MAXN];
struct cmp{
	bool operator()(pll a,pll b){
		if(a.first!=b.first){
			return a.first>b.first;
		}
		if(a.second!=b.second){
			return a.second>b.second;
		}
		return false;
	}
};

void solve(){
	std::cin>>N;
	// 里面装的东西，容器，以及比较规则
	std::priority_queue<pll,std::vector<pll>,cmp > pq;
	// needBack指的是这之前的数都要往后移
	ll needBack=0;
	for(int i=1;i<=N;++i){
		std::cin>>A[i];
		pq.push({A[i],i});
	}
	// back是指被移到后面的哪个位置（即移到原来的N+back）
	ll idx=0,back=1;
	// 每一个位置最多被移动一次，所以复杂度不会太高。
	while (!pq.empty()) {
		pll temp=pq.top();
		pq.pop();
		if(temp.second>needBack){
			Ans[++idx]=temp.first;
			needBack=temp.second;
		}else{
			pq.push({temp.first+1,N+back});
			back+=1;
		}
	}
	for(int i=1;i<=N;++i){
		std::cout<<Ans[i]<<" ";
	}
	std::cout<<"\n";
	return;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}

心路历程（WA，TLE，MLE……）