UVa1611 Crane [思维/模拟]

Author Avatar
空気浮遊 2018年06月11日
  • 在其它设备中阅读本文章
  • 模拟
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

我原本还是能够想出解法的...
然而事实上我还是考虑过多了...
大概说明我不擅长骗分....

Problem

输入 n 个数要求把它变成升序排列,每次操作都可以交换一个长度为偶数区间的左右两半
$n\leq 10000$
有多组数据

Solution

题目给开了三秒。

正解思路是每次找序列最小值。

然后用 $\leq 3$ 次操作旋到对应的位置。

所以每次对一个值操作可以用不超过 $O(2n)$ 的时间。

因此时间复杂度是 $O(n^2)$ 的。

理论上数据不超过三组可过。

但我掐指一算,数据肯定不止三组呀?

于是我就没用这个方法了。

我用了个更蠢的
就是冒泡排序法
先随机交换个 100 遍再说
果然炸了

于是换成了原来的方法

210ms....

Code

// Code by ajcxsu
// Problem: crane

#include<bits/stdc++.h>
using namespace std;

const int N=10010;
int arr[N];
int n;

void inv(int l, int r) {
    int mid=l+(r-l+1)/2;
    while(mid<=r) swap(arr[l++], arr[mid++]);
}
int opt[1000000][2], p;

int main() {
    srand(time(NULL));
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--) {
        cin>>n;
        p=0;
        int nl, nr, len;
        for(int i=1;i<=n;i++) cin>>arr[i];
        for(int i=1;i<=n;i++) {
            for(nr=i;nr<=n;nr++)
                if(arr[nr]==i) break;
            len=nr-i+1;
            if(len==1) continue;
            else if(len==2) inv(i, i+1), opt[++p][0]=i, opt[p][1]=i+1;
            else if(len&1) {
                inv(i+1, nr);
                inv(i, nr-1);
                opt[++p][0]=i+1, opt[p][1]=nr;
                opt[++p][0]=i, opt[p][1]=nr-1;
            }
            else {
                inv(i+2, nr);
                inv(i+1, nr-1);
                inv(i, i+1);
                opt[++p][0]=i+2, opt[p][1]=nr;
                opt[++p][0]=i+1, opt[p][1]=nr-1;
                opt[++p][0]=i, opt[p][1]=i+1;
            }
        }
        cout<<p<<endl;
        for(int i=1;i<=p;i++)
            cout<<opt[i][0]<<' '<<opt[i][1]<<endl;
    }
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-uva-1611.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material