算法分析实验之翻煎饼

题目描述

麦兜最喜欢的食物是煎饼，每次在街上看到煎饼摊的时候都会在那里停留几分钟。最吸引麦兜还是煎饼师傅那一手熟练的翻煎饼的技术，一堆煎饼在那里，师傅只需要用铲子翻几下，就让煎饼整齐的叠在了一起。 这天，为了庆祝麦兜被保送上研究生，他从煎饼师傅那里买回来一些煎饼请客。但是麦兜买回的煎饼大小不一，麦兜太想吃煎饼了，他想吃这些煎饼中最大的那个。麦兜还知道同学们也很喜欢煎饼，为了表示他的诚意，他想让同学们先吃，麦兜最后吃，因此，麦兜想把煎饼按照从小到大的顺序叠放在一起，大的在最下面。这样麦兜就可以在最后拿到最大的那一块煎饼了。 现在请你帮助麦兜用煎饼师傅翻煎饼的方法把麦兜买的煎饼从小到大的叠在一起。煎饼师傅的方法是用铲子插入两块煎饼之间，然后将铲子上的煎饼翻一转，这样铲子上第一个煎饼就被翻到了顶上，而原来顶上的煎饼则被翻到了刚才插入铲子的地方。麦兜希望这样翻煎饼的次数最少。

输入

输入包括两行，第一行是一个整数n(1<=n<=1000)，表示煎饼的个数，接下来的一行有n个不相同的整数，整数间用空格隔开，每个整数表示煎饼的大小（直径），左边表示顶部，右边表示底部。

输出

输出为一行，翻煎饼的最少次数

样例输入复制

5
5 4 2 3 1

样例输出

4


对于样例的分析：
5 4 2 3 1 （最大的煎饼在顶部，反转一次让它在底部，整个数组都要倒序）　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　翻转次数：0
1 3 2 4 5 （最大的煎饼已经在底部了，接着找第二大的煎饼，发现也在底部了，这里的底部是指n-1的位置，接着就是第三大的煎饼 3 了）　　　 翻转次数：1
3 1 2 4 5 （最大的煎饼在顶部，反转一次让它在底部，3到2整个数组都要倒序）　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　翻转次数：2
2 1 3 4 5 （此时的最大的煎饼变成了2，将铲子插到2和1之间，翻转一次）　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 翻转次数：3
1 2 3 4 5　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　翻转次数：4

解析：题目中标记的地方为解题的重点部分，本题的关键是最大的煎饼的位置。
　　它的位置可以有三个：
　　　　1、在顶部
　　　　2、在底部
　　　　3、在中间
然而，当它在中间的时候，我们可以通过翻转让它在顶部位置，减少代码量；

#include<iostream>
using namespace std;
int n;
int sum=0;
int a[1005];
int J()
{
    if(n==0) return 0;
    int j=0;int max=0;
    for(int i=0;i<n;i++)
    if(a[i]>=max)
    {
        max=a[i];
        j=i;
    }
    
     if(j==n-1)//最大煎饼在底部 
    {
        n--;
        J();
    }
    else if(j==0){//最大煎饼在顶部，整个数组倒序 
        sum++;
        for(int i=n-1;i>j;i--)
        {
            int t=a[j];
            a[j]=a[i];
            a[i]=t;
            j++;
        }
        n--;
        J();
    }
    else{//最大煎饼不在顶部，不在底部，反转一次，数组部分倒序，使最大煎饼到顶部，执行上一步 
        sum++;
        for(int i=0;i<j;i++)
        {
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
            j--;
            
        }
        J();
    }
}
int main(){
    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i];
    J();
    cout<<sum<<endl;
    return 0;
}