AcWing 3802. 消灭数组

原题链接

题目描述

给定一个长度为 $n$ 的数组，如果它不是非降序（非严格单调递增）的，那么就将它的前半部分或后半部分消灭。

不断重复这个消灭一半数组的过程，直至数组变为升序为止。

请问，得以幸存的数组的最大可能长度是多少？

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$，表示给定数组。

输出格式

输出幸存数组的最大可能长度。

数据范围

$1≤T≤10$
$1≤n≤16$，$n$ 保证是 $2$ 的整数次幂。
$1≤a_i≤100$

样例

输入样例：

3
4
1 2 2 4
8
11 12 1 2 13 14 3 4
4
7 6 5 4

输出样例：

4
2
1

思路

当当前区间为升序的时候，直接返回当前区间的长度即可。

否则递归求解当前区间的前半段和后半段，取最大值即可。

代码

C++

#include <iostream>

using namespace std;

const int N = 20;
int a[N];

int worker(int l, int r)
{
    // l ~ r区间只有一个数，那么长度就是1
    if ( l == r ) return 1;
    bool f = true;
    // 判断l ~ r这个区间是否是升序的。
    for ( int i = l; i + 1 <= r; i++ )
        if ( a[i] > a[i + 1] )
        {
            f = false;
            break;
        }
    // 如果l ~ r这个区间是升序的，那么就返回这段区间的长度
    if ( f ) return r - l + 1;
    // 题目保证 n 是 2 的整数次幂，所以不需要考虑奇数的情况。
    int m = l + r >> 1;
    // 递归求解
    return max(worker(l, m), worker(m + 1, r));
}

int main()
{
    int T, n;
    cin >> T;
    while ( T-- )
    {
        cin >> n;
        for ( int i = 0; i < n; i++ ) cin >> a[i];
        cout << worker(0, n - 1) << endl;
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    static final int N = 20;
    static int a[] = new int[N];
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T-- > 0 )
        {
            int n = in.nextInt();
            for ( int i = 0; i < n; i ++ ) a[i] = in.nextInt();
            System.out.printf("%d\n", worker(0, n - 1));
        }
    }
    
    public static int worker(int l, int r)
    {
        if ( l == r ) return 1;
        boolean f = true;
        for ( int i = l; i + 1 <= r; i ++ )
            if ( a[i] > a[i + 1] )
            {
                f = false;
                break;
            }
        if ( f ) return r - l + 1;
        int m = l + r >> 1;
        return Math.max(worker(l, m), worker(m + 1, r));
    }
}