SWUST OJ 254: 翻煎饼

电玩女神 2024-04-01 09:40 89阅读 0赞

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

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

**输出**

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

**样例输入**

5
    5 4 2 3 1

**样例输出**

**实现思路**  
我们首先要读懂题，铲子插入两块煎饼之间怎么翻转，举个例子吧，5 4 2 3 1，比如插在4到2中间，翻转就变成了245 31(就是把铲子上面的和铲子下面的一个翻转)  
为什么四次我先把步骤写下

第一次  1 3 2 4 5
    第二次  3 1 2 4 5
    第三次  2 1 3 4 5
    第四次  1 2 3 4 5

思想:就是把最大值反转在数组中第一个位置，返回第二次反转才能变成最后一个位置  
1.首先我们要找到最大值，进行反转，我们要判断最大位置是不是在最后位置(我们从右到左依次从大到小)，如果是就不需要反转，否则就需要反转  
2.我们需要考虑两次反转，第一次反转是最大值反转，如果在数组中索引位置为0(就是第一个，那么我们就不需要反转)，第二次反转就是把数组中的第一个翻转到最后

import java.util.Scanner;
    
    public class Pancake {
        
        public static int count = 0;
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
        
                arr[i] = sc.nextInt();
            }
            for (int i = arr.length-1; i >= 0; i--) {
        
                int index = findMax(arr,i);
                if (arr[i] != arr[index]){
        
                    arr = reverse(arr,index);
                    arr = reverse(arr,i);
                }
            }
            System.out.println(count);
        }
    
        private static int[] reverse(int[] arr, int i) {
        
            if (i != 0){
        
                int l = 0;
                while (l<i){
        
                    int temp = arr[l];
                    arr[l++] = arr[i];
                    arr[i--] = temp;
                }
                count++;
            }
            return arr;
        }
    
        private static int findMax(int[] arr, int i) {
        
            int max = 0;
            int index = 0;
            for (int j = 0; j <= i; j++) {
        
                if (arr[j]>max){
        
                    max = arr[j];
                    index = j;
                }
            }
            return index;
        }
    }