HihoCoder 1409 Smallest Sub Array

发表于 | 分类于 | 阅读次数: |
字数统计: 679 | 阅读时长 ≈ 3

1409 : Smallest Sub Array

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

Given an array of integers A, find the smallest contiguous sub array B of A such that when you sort B in ascending order the whole array A becomes sorted as well.

For example if A = [1, 2, 3, 7, 4, 6, 5, 8] the smallest B will be [7, 4, 6, 5].

输入

The first line contains an integer N denoting the length of A. (1 <= N <= 100000)

The second line contains N integers denoting the array A. (0 <= Ai <= 100000000)

输出

The length of the smalltest sub array B.

样例输入

8
1 2 3 7 4 6 5 8

样例输出

4

题解

题目大意是给一个数组 A ，找到最小长度的子序列，使排序这段子序列之后整个数组有序。
方法一：
输入 A 数组的时候记录 B 数组，将 A 数组排序，从头开始一一比对 B 数组中的元素，若 B 数组有一个元素与排序后的 A 数组不同，则记录此时的下标。再反之从尾开始一一比对，记录不同的元素的下标。用这两个下标相减再加一就可得到答案。
方法二：
在 A 数组中从下标为 1 开始，记录第一个符合 A[i] < A[i - 1] 这个条件的 i - 1 的下标。同理，从 n - 1 开始，记录第一个符合 a[i] < a[i - 1] 这个条件的 i 的下标。用这两个下标相减再加一就可得到答案。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//方法一
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#define ll long long
#define ull_ unsigned long long

using namespace std ;

int main(){
    int n ;
    while ( cin >> n ){
        int a[n + 10] , b[n + 10] ;
        for ( int i = 0 ; i < n ; i ++ ){
            cin >> a[i] ;
            b[i] = a[i] ;
        }
        sort(a , a + n) ;
        int l , r ;
        for ( int i = 0 ; i < n ; i ++ ){
            if ( b[i] != a[i] ){
                l = i ;
                break ;
            }
        }
        for ( int i = n - 1 ; i >= 0 ; i -- ){
            if ( b[i] != a[i] ){
                r = i ;
                break ;
            }
        }
        cout << r - l + 1 << endl ;
    }
    return 0 ;
}

//方法二
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#define ll long long
#define ull_ unsigned long long

using namespace std ;

int main(){
    int n ;
    while ( cin >> n ){
        int a[n + 10] ;
        for ( int i = 0 ; i < n ; i ++ ){
            cin >> a[i] ;
        }
        int l , r ;
        for ( int i = 1 ; i < n ; i ++ ){
            if ( a[i] < a[i - 1] ){
                l = i - 1 ;
                break ;
            }
        }
        for ( int i = n - 1 ; i >= 1 ; i -- ){
            if ( a[i] < a[i - 1] ){
                r = i ;
                break ;
            }
        }
        cout << r - l + 1 << endl ;
    }
    return 0 ;
}