F. Cyclic Shifts Sorting
题意
给出一个数组a 长度为n<500
要求给它排序 一次排序操作是对[ai,ai+1,ai+2]内的元素整体顺时针移动
变为[ai+2,ai,ai+1]
最多不超过n^2次操作 是否能将原数组排序成非降序
输出操作次数 并输出需要对哪个区间进行顺时针移动
题解
先简化问题 如果这个数组是长度为n的排列，即只有[1,2,3…n]各一个
那么在这种情况下 当且仅当排列中的逆序对为偶数时存在解
因为一次顺时针操移动作后 整个排列的逆序对的奇偶性是不变的
若原来有奇数个逆序对那么无论怎么操作最后仍然会剩下一个逆序对无法被排序
若有偶数对逆序对 那么对该排列模拟 选择排序 的过程 找到数组内
第i小的移动到从左到右第i位
那么 对于非排列的数组a ，其中存在重复的数组如何解决呢
首先离散化原数组a (根据pair(ai,i)以值为第一关键字 下标为第二关键字sort )
再根据原数组生成一个对应的排列b
若排列b中有奇数个逆序对 那么尝试找到原数组a中两个相同的数
交换它们在排列b中的位置 使得总的逆序对个数-1 成为偶数
因为a中相同的数被离散化后在排列b是两个不同的数 它们可能产生一对逆序对 而实际上它们不需要被交换，之后再对生成的排列b进行模拟选择排序的过程
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
typedef pair<ll,ll> P;
const int mod=2e3;
const int Max=4e5+5;
ll data[Max],ndata[Max];
struct Data{
int indx;
int val;
};
inline rerange(int pos){
int a=ndata[pos],b=ndata[pos+1],c=ndata[pos+2];
ndata[pos]=c,ndata[pos+1]=a,ndata[pos+2]=b;
}
bool cmp(Data a,Data b){
if(a.val!=b.val)return a.val<b.val;
return a.indx<b.indx;
}
int main(){
Turnoff;
int t;cin>>t;
while(t--){
int n;cin>>n;
vector<Data>sdata;
vector<int>step;
for(int i=0;i<n;i++){
cin>>data[i];
Data temp;
temp.indx=i,temp.val=data[i];
sdata.push_back(temp);
}
sort(sdata.begin(),sdata.end(),cmp);
for(int i=0;i<n;i++)ndata[sdata[i].indx]=i+1;
int invers=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++)if(ndata[j]<ndata[i])invers++;
}
if(invers&1){
bool flag=1;
for(int i=0;i<n-1;i++){
if(sdata[i].val==sdata[i+1].val){
swap(ndata[sdata[i].indx],ndata[sdata[i+1].indx]);
flag=0;break;
}
}
if(flag){
cout<<-1<<endl;
continue;
}
}
int inplace=0;
while(inplace<n){
int pos=-1;
for(int i=inplace;i<n;i++){
if(ndata[i]==inplace+1){
pos=i;
break;
}
}
for(int i=pos-2;i>=inplace;i-=2){
rerange(i);
step.push_back(i+1);
}
if(ndata[inplace+1]==inplace+1){
rerange(inplace);
rerange(inplace);
step.push_back(inplace+1);
step.push_back(inplace+1);
}
inplace++;
}
cout<<step.size()<<endl;
for(auto i:step)cout<<i<<" ";
cout<<endl;
}
return 0;
}
|