Codeforces 1374 F. Cyclic Shifts Sorting —— 暴力，贪心

This way

题意：

给你一个长度为n的串，你每次可以选择一个点i，然后将$a_i,a_{i+1},a_{i+2}$循环向右移位一次。让你输出选择的点的次序使得最终的这个串递增。你最多可以使用的操作次数不超过$n^2$

题解：

这个的话，我以为我想错了，为什么会这么简单呢。 就从小到大枚举每个位置，然后找到未排序的最小的点的最前面的位置，然后一次往前移两格，直到当前位置或者当前位置+1的地方，如果是当前位置+1的地方的话，就再移两次即可。 然后最后两个数有可能是逆序的，但是不代表不能将他们正序，就像题目中样例的最后一个。 所以我们只需要从后往前再做一次像上面那样的操作即可。 最多的次数的话，应该是这么算的：假设每次都会交换最多次，也就是n/2+1次，然后(首项+末项)*项数/2*2的话，大概就是$\frac{n^2}{2}+2n$ 那么很明显在n>=3的情况下，它是不会超的。 时间复杂度$O(n)$

#include<bits/stdc++.h> using namespace std; const int N=505; int a[N]; vector<int>ans; int main() { int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); ans.clear(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int p=1; while(p<=n-2){ int u=p; for(int i=p+1;i<=n;i++) if(a[i]<a[u]) u=i; while(u-2>=p) swap(a[u],a[u-2]),swap(a[u],a[u-1]),u-=2,ans.push_back(u); if(u==p+1) swap(a[u-1],a[u+1]),swap(a[u-1],a[u]),u--,ans.push_back(u),ans.push_back(u); p++; } p=n; while(p>=3){ int u=p; for(int i=p-1;i;i--) if(a[i]>a[u]) u=i; while(u+2<=p) swap(a[u],a[u+2]),swap(a[u],a[u+1]),u+=2,ans.push_back(u-2),ans.push_back(u-2); if(u==p-1) swap(a[u+1],a[u-1]),swap(a[u],a[u+1]),u++,ans.push_back(u-2); p--; } int f=0; for(int i=1;i<n;i++) if(a[i]>a[i+1]) f=1; if(f) printf("-1\n"); else { printf("%d\n",ans.size()); for(int i:ans) printf("%d ",i); printf("\n"); } } return 0; }