Znzryb's Blog
0%

D. Darius' Wisdom

Posted on Edited on

思路讲解

总体我感觉没什么难的，就是写起来比较复杂

细节上的问题主要写在注释上，这里讲一下答题思路。

先把所有在应该放2位置的1换成2。（之前是没有这个步骤的，但好像导致策略不够优秀）

接着把所有在应该放2位置的0先换成1，再换成2

最后放一下1就可以了

AC代码

https://codeforces.com/contest/2034/submission/297475528

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#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

判断哪里应该是2，哪里应该是1的判断有点问题

WA2:

https://codeforces.com/contest/2034/submission/297454477

策略不够优，超过了最大允许操作次数