牛牛与交换排序-白红宇的个人博客

牛牛与交换排序

发布日期：2021-05-08 11:20:18 浏览次数：14 分类：精选文章

本文共 3518 字，大约阅读时间需要 11 分钟。

翻转操作是一种有效的数组调整方法，常用于解决数组错位问题。通过合理选择翻转区间，可以逐步将数组恢复到正确的顺序。以下是通过模拟翻转操作来解决这个问题的详细思路：

模拟翻转操作的思路

问题分析：

给定一个整数数组，其中元素可能存在错位。目标是通过最少的翻转操作，将数组恢复为1, 2, 3, ..., n的顺序。

每次翻转操作选择一个区间，将区间内的元素顺序反转。

关键观察：

翻转操作会影响区间内元素的顺序，正确选择翻转区间是恢复数组的关键。

每次翻转后，数组中的某些元素可能已经处于正确的位置，后续的翻转需要围绕这些已正确元素进行。

模拟方法：

使用双端队列（deque）来模拟翻转操作。双端队列支持高效的插入和删除操作，适合处理前后元素的调整。

记录翻转操作的次数，并判断是否已经完成了足够的翻转，使得数组恢复正确。

具体步骤：

初始化：读取输入数组，初始化双端队列。

确定翻转区间：找到第一个错误的位置，确定需要翻转的区间长度。

处理翻转操作：根据翻转次数（奇数或偶数），调整队列中的元素，模拟翻转效果。

验证结果：检查队列中的元素是否恢复到正确的顺序，确定翻转是否完成。

代码实现

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);        int n;    cin >> n;    array
      
        arr(n + 1, 0);    for (int i = 1; i <= n; ++i) {        cin >> arr[i];    }        bool flag = true;    int pos = -1;    for (int i = 1; i <= n; ++i) {        if (arr[i] != i) {            pos = i;            break;        }    }        if (pos == -1) {        cout << "yes\n1";        return 0;    }        int k = 0;    for (int i = pos; i <= n; ++i) {        if (arr[i] == pos) {            k = i - pos + 1;            break;        }    }        deque
       
         q;    for (int i = pos; i <= pos + k - 1; ++i) {        q.push_back(arr[i]);    }        for (int i = pos; i + k - 1 <= n; ++i) {        if (flag) {            if (q.front() != i) {                flag = false;                if (q.back() != i) {                    q.pop_back();                    if (i + k <= n) {                        q.push_front(arr[i + k]);                    }                } else {                    q.pop_front();                    if (i + k <= n) {                        q.push_back(arr[i + k]);                    }                }            } else {                if (q.back() != i) {                    flag = false;                    q.pop_front();                    if (i + k <= n) {                        q.push_back(arr[i + k]);                    }                } else {                    int x = q.back();                    q.pop_back();                    if (i + k <= n) {                        q.push_front(arr[i + k]);                    }                }            }        } else {            if (q.back() != i) {                flag = false;                q.pop_front();                if (i + k <= n) {                    q.push_back(arr[i + k]);                }            } else {                int x = q.back();                q.pop_back();                if (i + k <= n) {                    q.push_front(arr[i + k]);                }            }        }    }        if (flag) {        bool valid = true;        while (!q.empty()) {            int x = q.front();            q.pop_front();            if (x != q.front()) {                valid = false;                break;            }        }        if (valid) {            cout << "yes\n1";        } else {            cout << "no\n-1";        }    } else {        bool valid = true;        while (!q.empty()) {            int x = q.front();            q.pop_front();            if (x != q.front()) {                valid = false;                break;            }        }        if (valid) {            cout << "yes\n1";        } else {            cout << "no\n-1";        }    }        return 0;}

代码解释

输入处理：

读取输入数组，并初始化双端队列。

确定翻转起点：

找到第一个错误的位置，确定需要翻转的区间长度。

初始队列填充：

将需要翻转的区间内的元素加入双端队列。

翻转操作模拟：

根据翻转次数（奇数或偶数），调整队列中的元素，模拟翻转效果。

结果验证：

检查队列中的元素是否恢复到正确的顺序，输出结果。

通过上述方法，可以有效地模拟翻转操作，并判断数组是否可以通过翻转恢复到正确的顺序。

上一篇：牛牛与跷跷板

下一篇：牛牛的质因数

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

模拟翻转操作的思路

代码实现

代码解释

发表评论

最新留言

关于作者

推荐文章