祎隋

32.sort
Description众所周知,排序方法有许多种。例如:简单易懂的冒泡排序,平均复杂度较优的快速排序,以及不基于比...
扫描右侧二维码阅读全文
15
2019/02

32.sort

Description

众所周知,排序方法有许多种。例如:简单易懂的冒泡排序,平均复杂度较优的快速排序,以及不基于比较的基数排序等等。

现在,小 DD 得到了一个自然数序列 {a1,a2,⋯,an}{a1,a2,⋯,an}。他想要对其按照从小到大的顺序进行排序(即使得每个元素均严格不大于他的后继元素)。但由于基于比较的排序算法复杂度下界已经被证明为 Θ(nlog2n)Θ(nlog2⁡n),所以小 DD 决定尝试一种全新的排序算法:翻转排序。

在翻转排序中,小 DD 在每次操作中,可以选择一个区间 l,r (1≤l≤r≤n)(1≤l≤r≤n),并翻转 al,al+1,⋯,aral,al+1,⋯,ar。即,在该次操作完后,序列将会变为 a1,a2,⋯,al−1,ar,ar−1,⋯,al+1,al,ar+1,ar+2,⋯,ana1,a2,⋯,al−1,ar,ar−1,⋯,al+1,al,ar+1,ar+2,⋯,an。

例如,对于序列 1,6,2,4,3,5,若选择区间 2,4 进行翻转,则将会得到 1,4,2,6,3,5。

定义一次操作的代价为 r−l+1r−l+1,即翻转的区间长度。定义一个操作序列的代价为每次操作的代价之和。现在,请你帮助小 DD 求出一个代价足够小的操作序列(你并不一定要求出代价最小的操作序列)。

Input

第一行一个正整数 nn,表示序列长度。

第二行 nn 个空格隔开的非负整数,表示小 DD 得到的自然数序列 a1,a2,⋯,ana1,a2,⋯,an。

Output

输出若干行,每行两个空格隔开的正整数 l,rl,r (1≤l≤r≤n)(1≤l≤r≤n),表示一次翻转区间 l,r 的操作。

最后输出一行 -1 -1,标志着操作序列的结束。

Sample Input

4 1 3 2 4

Sample Output

2 3 -1 -1

Hint

1.下发文件中提供了 checker.cpp,该程序将对于其所在目录下的 sort.in,判断其所在目录下的 sort.out 是否为一个正确的操作序列。若正确,将给出该操作序列的代价。若不正确,将给出错误信息。选手可以借助该程序来更好地检查自己的程序是否正确。

运行时,必须保证 sort.in 为一个合法的输入,且需保证 sort.out 符合题目中描述的输出格式,否则出现任何结果均有可能。

2.对于所有测试数据,保证 1≤n≤500001≤n≤50000,且 0≤ai≤1090≤ai≤109。

(附checker.cpp)

#include <algorithm>
#include <cstdio>
int arr[50005];
int main()
{
    FILE *fin = fopen("sort.in", "r"), *fout = fopen("sort.out", "r");
    if (!fin)
    {
        puts("INVALID : File sort.in not found.");
        return -1;
    }
    if (!fout)
    {
        puts("INVALID : File sort.out not found.");
        return -1;
    }
    int n;
    fscanf(fin, "%d", &n);
    for (int i = 0; i < n; i++)
        fscanf(fin, "%d", arr + i);
    int l, r, sum = 0;
    while (~fscanf(fout, "%d%d", &l, &r))
    {
        if (l == -1 && r == -1)
            break;
        sum += r - l + 1;
        if (l <= 0 || l > n)
        {
            printf("INVALID : l = %d is not in range [1, %d].\n", l, n);
            return -1;
        }
        if (r <= 0 || r > n)
        {
            printf("INVALID : r = %d is not in range [1, %d].\n", r, n);
            return -1;
        }
        if (l > r)
        {
            printf("INVALID : %d = l > r = %d.\n", l, r);
            return -1;
        }
        if (sum > 20000000)
        {
            puts("INVALID : Too much cost.");
            return -1;
        }
        std::reverse(arr + --l, arr + r);
    }
    bool f = true;
    for (int i = 1; i < n; i++)
        f &= arr[i] >= arr[i - 1];
    if (!f)
    {
        puts("INVALID : Not sorted.");
        return -1;
    }
    printf("VALID : Total cost is %d.\n", sum);
    return 0;
}

checker

Solution

本题算是一个比较新颖的题目,实际上是用这种翻转来模拟实现归并排序:

先将给定数列进行离散化,每次选定一个中间的数,将小于等于它的排在左边,大于它的排在右边,再依次递归两边就可以了;

主要是复杂度(进行操作的次数)证明a.... 排一遍要n,由于其非01性,所以进行log2n次的n排,故排一遍将l到r以stdd为标准换为左边小于等于stdd,右边大于等于stdd的操作数为$Θ(nlog^2n)$ ;

$T(n) = 2T(n/2) + Θ(nlog^2n)$,可以解得 $T(n) = Θ(nlog^2n)$ ; tql%%%
上代码。

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int n,pos[maxn];
struct node{
    int v,id;
    friend bool operator<(node a,node b){
        return a.v<b.v;
    }
}nd[maxn];
int stdd;
void run(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    run(l,mid);run(mid+1,r);
    
    int L,R;//要翻转的区间 
    L=R=mid;//L和R的初值 
    int i=mid,j=mid+1;
    while(i>=l&&pos[i]>stdd) L=i--;
    while(j<=r&&pos[j]<=stdd) R=j++;
    if(L!=R){
        printf("%d %d\n",L,R);
        reverse(pos+L,pos+R+1);
    } 
} 
void msort(int l,int r){
    if(l==r) return;
    
    int mid=stdd=(l+r)>>1;
    run(l,r);//将l到r以stdd为标准换为左边小于等于stdd,右边大于等于stdd
 
    msort(l,mid);msort(mid+1,r);    
}
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&nd[i].v);nd[i].id=i;
    }
    sort(nd+1,nd+n+1);
    for(int i=1;i<=n;i++) pos[nd[i].id]=i;//离散化位置确定 
    
    msort(1,n);
    printf("-1 -1\n");
}
int main(){
    //freopen("sort.in","r",stdin);
    //freopen("sort.out","w",stdout);
    init();
 
    return 0;
}
Last modification:March 2nd, 2019 at 10:35 am

Leave a Comment