题目描述

输入

输出

样例输入

样例输出

源代码

方法1

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 1001
using namespace std;

int n, ans, a[N];
void change(int x)
{
    
	   int l, r;
	    ans++;
	    l = r = x / 2;
	    r++;
	    if (x % 2 == 1) r++;
	    while (l > 0) swap(a[l--], a[r++]);
	}
 int main()
 {
    
	     int i, k;
	     scanf("%d", &n);
	     for (i = 1; i <= n; i++) scanf("%d", &a[i]);
	     ans = 0;
	     while (n > 1)
		     {
    
		         k = 1;
		         for (i = 2; i <= n; i++)
			        {
    
			             if (a[k] < a[i]) k = i;
			         }
		         if (k != n)
			         {
    
			             if (k > 1) change(k);
			             change(n);
			         }
		        n--;
		     }
	    printf("%d\n", ans);
	    return 0;
	}

方法2

#include<stdio.h>
#include<stdlib.h>
int a[1002]={
    0};
bool flag=true;//Whether it satisfies the non-small-to-large order 
int dex=0;//The number of already queued positions 
int conut=0;//最大值下标 
int ans=0; //翻转次数 
void print(int n){
    
	for(int i=1;i<=n;i++){
    
		printf("%d ",a[i]);
	}
	printf("\n");
}
void juge(int n){
    
	int flag1=0 ;
	for(int i=1;i<=n-1;i++){
    
		if(a[i]>a[i+1]){
    
			flag=true;
			flag1++;
		}
	}
	if(flag1==0){
    
	   flag=false;
	}
	
}
void turn(int n){
    //翻转函数
	//Flip the first time
	int low=1,high=conut;
	if(conut!=1){
    //Top and without flipping
	    while(low<=high){
    
	    	int temp=a[low];
			a[low]=a[high];
			a[high]=temp;
			low++;
			high--; 
		}
// print(n) 
		ans++;
	}
	juge(n);//Determine whether it is ordered from small to large
	if(flag==false){
    
	return ;
	}
	//Flip a second time 
	low=1,high=n-dex;
	while(low<=high){
    
    	int temp=a[low];
		a[low]=a[high];
		a[high]=temp;
		low++;
		high--;
	}
// print(n);
	ans++;
	juge(n);//Determine whether it is ordered from small to large 
	dex++;
}
void find(int n){
    //查找元素 
    int max=-1;
    for(int i=1;i<=n-dex;i++){
    
     	if(a[i]>=max){
    
     		max=a[i];
     		conut=i;
		}
	}
	if(conut==n-dex){
    //The current position is already the maximum position 
		dex++;
		find(n);	
	}
	else 
	return ;
} 
int main(){
    
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
	}
	juge(n);//Determine whether it is ordered from small to large 防止BUG 
	while(flag&&dex!=n-1){
    
		find(n);
		turn(n);
	}
	printf("%d\n",ans);
} 

关于这题

这里解释一下第一种方法
思路：Find the largest number first Move him to the front 再翻转
At this point the maximum number has reached the end We will no longer deal with him Look at the previous elements
That is, to deal with the subarray problem
注：We have to judge alone The largest number is the last one 不然会出BUG
这里ans 和 数组 We are setting up global variables Because it is also used in the function
l 和 r is to determine the position of the array left mark and 右标 当 x%2==1时 Add one to the right mark （Don't mark the number in the middle）