CF 990-D. Move Back at a Cost · znzryb
## 思路讲解
我看题解说，注意到，**每个块最多被move back一次**，那为什么最多被移动一次那？
我个人的理解是因为我们是可以随意选择move back的顺序，所以我们可以让我们的move back自动搞为一个单调的。
其实这个题解主要还是坚定了我的信心，让我知道我做法的时间复杂度是没问题的，我前面想复杂了。
总体上的思路是用数据结构优化模拟法，当然发现加粗（**每个块最多被move back一次**）是非常重要的，否则很容易想复杂。
核心是这段程序
```cpp
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](https://codeforces.com/contest/2047/submission/300222017)
```cpp
#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……）