确定数组是否可以通过旋转3个相邻的数组元素来排序？

Question

我有一个从1开始递增的自然数序列的排列，现在作为一个数组给出。如何判断这个数组能否通过旋转其中连续的3个元素来排序？

我已经实现了一个算法，基本上是将数组的索引与该索引处的元素进行比较。如果它们不相等，则调用choose_indices()函数，在数组中找到要交换的元素的正确位置后，选择包含待交换数字的3个连续元素并将其旋转。对于大小为n的数组，经过n-1次旋转后，数组就被排序了。如果数组可以使用3个连续元素旋转进行排序，此实现将返回true，但如果无法使用此方法对数组进行排序则会超时。

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
int n;
void rotate(vector<int> &arr,int end,int mid,int start)
{
    int temp=arr[start];
    arr[start]=arr[end];
    arr[end]=arr[mid];
    arr[mid]=temp;
}
void choose_indices(vector<int> &arr,int s,int q)
{
    for(int l=q;l<n;l++)
    {
        if(arr[l]==s)
        {
            if(l-q>=2)
            {
                rotate(arr,l,l-1,l-2);
                break;
            }
            else
            {
                rotate(arr,l+1,l,l-1);
                break;
            }
        }
    }
}
int main()
{
    vector<int> arr;
    int q,count=0;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>n;
        count=0;
        for(int i=0,p;i<n;i++)
        {
            cin>>p;
            arr.push_back(p);
        }
        for(int j=0,k=1;j<n && k<n; )
        {
            if(arr[j]!=k)
            {
                choose_indices(arr,k,j);
                if(arr[j]==k)
                {
                    j++;
                    k++;
                    count++;
                }
            }
            else
            {
                j++;
                k++;
                count++;
            }
        }
        if(count==n-1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
           cout<<"NO"<<endl;
        }
        arr.clear();
    }
}

示例输入： 1 2 3 5 4

针对此输入，我的代码出现了运行时错误。 如何判断给定的数组是否无法使用连续3个元素的旋转进行排序？

- Shantanu

---

什么错误？ - Joseph D.

1 5 1 2 3 5 4 不是“自然数序列的排列”。 - Igor Tandetnik

如果你只需要确定一个数组是否可以这样排序（而不是实际排序它），那应该很简单。计算逆序对的数量（相对于彼此顺序错误的元素对）- 如果是偶数，数组可以排序，如果是奇数，则不能。这是因为每次旋转都会添加或删除两个逆序对（假设不存在相等的元素，就像数组实际上是自然数序列的排列一样）。至少我这么认为，脑海中想到的。 - Igor Tandetnik

1 代表查询的数量，5 表示数组的大小。 - Shantanu

Answer 1

旋转三个相邻元素始终会消除2个逆序对，如果存在的话，或者引入2个逆序对。

考虑以下情况：

1 2 3 5 4

无论你旋转多少次，都只有1个反演，如果不引入其他反演，你永远无法取消该反演，因为你总是旋转3个连续的元素。

因此，只需计算反演数，如果反演数为奇数，则答案为NO，否则为YES。有高效的算法可以计算反演数（如归并排序）。

- Sumeet

---

这是我一开始想的，但问题在于我必须设计出同样能够完成这两个任务的算法。 - Shantanu

你是指两个工作吗？ - Sumeet

如果数组可以排序，则输出应为“是”，但如果不能，则应返回“否”。 - Shantanu

你不需要实际进行任何旋转并查看是否可以排序。 - Sumeet

只需计算逆序对的数量并获得布尔答案。这有什么大不了的？ - Sumeet

Answer 2

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
int n;
void rotate(vector<int> &arr,int end,int mid,int start)
{
    int temp=arr[start];
    arr[start]=arr[end];
    arr[end]=arr[mid];
    arr[mid]=temp;
}
void choose_indices(vector<int> &arr,int s,int q)
{
    for(int l=q;l<n;l++)
    {
        if(arr[l]==s)
        {
            if(l-q>=2)
            {
                rotate(arr,l,l-1,l-2);
                break;
            }
            else
            {
                rotate(arr,l+1,l,l-1);
                break;
            }
        }
    }
}
int main()
{
    vector<int> arr;
    int q,count=0;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>n;
        count=0;
        for(int i=0,p;i<n;i++)
        {
            cin>>p;
            arr.push_back(p);
        }
        //Counting the number of inversion in the array
        int ctiv=0;
        for(int r=0;r<n;r++)
        {
            for(int s=r+1;s<n;s++)
            {
                if(arr[r]>arr[s] && r<s)
                {
                    ctiv++;
                }
            }
        }
        if(ctiv%2!=0)
        {
            cout<<"NO"<<endl;
        }
        else 
        {
            for(int j=0,k=1;j<n && k<n; )
            {
                if(arr[j]!=k)
                {
                    choose_indices(arr,k,j);
                    if(arr[j]==k)
                    {
                        j++;
                        k++;
                        count++;
                    }
                }
                else
                {
                    j++;
                    k++;
                    count++;
                }
            }
            if(count==n-1)
            {
                cout<<"YES"<<endl;
            }
            arr.clear();
        }
    }
}

这是我设计的算法，用于判断给定的算法是否可以排序。如果可以排序，它将通过执行必要的3个连续旋转来对给定的数组进行排序。

- Shantanu