A. Thanos Sort time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Thanos sort is a supervillain sorting algorithm, which works as follows: if the array is not sorted, snap your fingers* to remove the first or the second half of the items, and repeat the process.

Given an input array, what is the size of the longest sorted array you can obtain from it using Thanos sort?

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

*Infinity Gauntlet required.

Input

The first line of input contains a single number nn (1≤n≤161≤n≤16) — the size of the array. nn is guaranteed to be a power of 2.

The second line of input contains nn space-separated integers aiai (1≤ai≤1001≤ai≤100) — the elements of the array.

Output

Return the maximal length of a sorted array you can obtain using Thanos sort. The elements of the array have to be sorted in non-decreasing order.

Examples Input Copy 
4
1 2 2 4
Output Copy 
4
Input Copy 
8
11 12 1 2 13 14 3 4
Output Copy 
2
Input Copy 
4
7 6 5 4
Output Copy 
1
Note

In the first example the array is already sorted, so no finger snaps are required.

In the second example the array actually has a subarray of 4 sorted elements, but you can not remove elements from different sides of the array in one finger snap. Each time you have to remove either the whole first half or the whole second half, so you'll have to snap your fingers twice to get to a 2-element sorted array.

In the third example the array is sorted in decreasing order, so you can only save one element from the ultimate destruction.

 

解题思路：就是告诉你有一种算法，它只能整体删除前半部分或者后半部分，使其升序的数目最多，我们可以先判断是否改数列使升序，然后如果不是，则不断递归左半部分和右半部分，取升序数目最大的；

代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int n ;
 5 int a[25];
 6 int mmx(int x , int y)
 7 {
 8     int sum = 1;   //注意这里sum从1开始；因为一个数字就算是升序；
 9     int flag = 1;
10     for(int i = x ; i < y ;i++)
11     {
12         if(a[i]<=a[i+1])  //看是否该序列已经升序；
13         {
14             sum++;
15         }else
16         {
17             flag = 0;   //一旦有不升序的就标记；
18         }
19     }
20     if(flag==1)
21     {
22         return sum ;
23     }else
24     if(flag==0)   //不断递归；
25     {
26         int m = (x+y)/2;
27         return max(mmx(x,m),mmx(m+1,y));//取最大；
28     }
29 }
30 int main()
31 {
32     int ans = 0;
33     cin>>n;
34     for(int i = 1 ; i <= n ;i++)
35     {
36         cin>>a[i];
37     }
38     ans = mmx(1,n);
39     cout<<ans;
40 }

 

 
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄