D. Darius' Wisdom · znzryb
## 思路讲解
总体我感觉没什么难的，就是写起来比较复杂
细节上的问题主要写在注释上，这里讲一下答题思路。
先把所有**在应该放2位置的**1换成2。（之前是没有这个步骤的，但好像导致策略不够优秀）
接着把所有**在应该放2位置的**0先换成1，再换成2
最后放一下1就可以了
## AC代码
[https://codeforces.com/contest/2034/submission/297475528](https://codeforces.com/contest/2034/submission/297475528)
```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>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
vector<ll> A(n+10);
vector<ll> test(n+10);
ll cnt2=0,cnt1=0;
// loc1Up指的是所有>n-cnt2的1.
vector<ll> loc1,loc2;
deque<ll> loc1Up,loc2Up;
vector<pair<ll, ll> > op;
for(int i=1;i<=n;++i){
cin>>A[i];
test[i]=A[i];
if(A[i]==2){
cnt2+=1,loc2.push_back(i);
}else if(A[i]==1)
cnt1+=1,loc1.push_back(i);
}
while(!loc1.empty()){
if(loc1.back()<=n-cnt2)
break;
loc1Up.push_front(loc1.back());
loc1.pop_back();
}
// loc2里装的是不符合要求的2.
while (!loc2.empty()) {
if(loc2.back()<=n-cnt2)
break;
// push_front 从前面加入，大的一直被往后面挤
// 保证loc2Up的递增性（idx的递增型）
loc2Up.push_front(loc2.back());
loc2.pop_back();
}
// ll idx=0;
// 这是排2的程序
// 先把所有1都搞过去
for(int i=n;i>n-cnt2;--i){
if(test[i]==1){
op.emplace_back(i,loc2.back());
swap(test[i], test[loc2.back()]);
loc1.push_back(loc2.back());
loc2.pop_back();
// loc1Up遵循递增顺序，遍历是递减
// 遇到先遇到的1必然最大的
loc1Up.pop_back();
}
}
for(int i=n;i>n-cnt2;--i){
if(loc2.empty())
break;
// A是不可靠的，需要用test
if(test[i]==2)
continue;
if(test[i]==1){
op.emplace_back(i,loc2.back());
swap(test[i], test[loc2.back()]);
loc1.push_back(loc2.back());
loc2.pop_back();
// loc1Up遵循递增顺序，遍历是递减
// 遇到先遇到的1必然最大的
loc1Up.pop_back();
}else{
// loc1不是空的时候
if(!loc1.empty()){
op.emplace_back(i,loc1.back());
swap(test[i], test[loc1.back()]);
op.emplace_back(i,loc2.back());
swap(test[i],test[loc2.back()]);
loc1.pop_back();
loc1.push_back(loc2.back());
loc2.pop_back();
}else {
op.emplace_back(i,loc1Up.back());
swap(test[i], test[loc1Up.back()]);
op.emplace_back(i,loc2.back());
swap(test[i], test[loc2.back()]);
loc1Up.pop_back();
// 这个1被交换到了loc2的位置
loc1.push_back(loc2.back());
loc2.pop_back();
}
}
}
// 这是排1的程序
vector<ll> is1(n+10,false);
sort(loc1.begin(), loc1.end());
while (!loc1.empty()) {
// n-cnt1-cnt2+1 需要摆1
// n-cnt1-cnt2 就不需要摆1了，所以break掉
if(loc1.back() <= n-cnt2-cnt1){
break;
}
is1[loc1.back()]=true;
loc1.pop_back();
}
// 开始正式排1
for(int i=n-cnt2;i>=n-cnt1-cnt2+1;--i){
if(loc1.empty())
break;
if(is1[i])
continue;
op.emplace_back(i,loc1.back());
swap(test[i], test[loc1.back()]);
loc1.pop_back();
}
cout<<op.size()<<endl;
for(int i=0;i<op.size();++i){
// if(abs(test[op[i].first]-test[op[i].second])!=1)
// cout<<"WA on this: ";
cout<<op[i].first<<" "<<op[i].second<<endl;
// swap(test[op[i].first], test[op[i].second]);
}
// cout<<"Outcome: ";
// for(int i=1;i<=n;++i){
// cout<<test[i]<<" ";
// }
// cout<<endl;
}
return 0;
}
/*
4
41 0 2 0
40 1 2 0
41 1 2 0
42 2 1 0
*/
```
## 心路历程（WA，TLE，MLE……）
WA1:
[https://codeforces.com/contest/2034/submission/297451161](https://codeforces.com/contest/2034/submission/297451161)
判断哪里应该是2，哪里应该是1的判断有点问题
WA2:
[https://codeforces.com/contest/2034/submission/297454477](https://codeforces.com/contest/2034/submission/297454477)
策略不够优，超过了最大允许操作次数