熊孩子拜访

熊孩子拜访

题目描述

已知存在一个长度为n的整数序列A，A中所有元素按照从小到大排序，现在执行倒置一段序列。请你找出A序列的倒置子序列。如果没有，输出“0 0”。

数据范围

1<=n<=1000

1<=num<=10000

样例输入

4

1 3 2 4

样例输出

2 3

代码

#include<stdio.h>

void quicksort(int *a,int left,int right)
{
    if(left>right)
    {
        return ;
    }
    int i=left;
    int j=right;
    int key=a[left];
    while(i!=j)
    {
        while(a[j]>=a[left]&&i<j)
        {
            j--;
        }
        while(a[i]<=a[left]&&i<j)
        {
            i++;
        }
        int s;
        s=a[i];
        a[i]=a[j];
        a[j]=s;
    }
    a[left]=a[i];
    a[i]=key;
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
}

int main(){
    int a[100000],b[100000];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    quicksort(b,0,n-1);
    int left = 0,right = 0;
    for(int i=0;i<n;i++){
        if(b[i]!=a[i]&&!left){
            left = i+1;
        }
        if(b[i]!=a[i]&&left!=0){
            right = i+1;
        }
    }
    printf("%d %d",left,right);
}