翻煎饼（Stacks of Flapjacks）-蓝桥杯练习

刺骨的言语ヽ痛彻心扉 2023-07-03 10:53 64阅读 0赞

# Stacks of Flapjacks UVA - 120 翻煎饼 #

## 问题 ##

堆栈和队列通常被认为是数据结构的面包和黄油，可用于体系结构、解析，操作系统和离散事件模拟。堆栈在形式语言理论中也很重要。  
现在的问题涉及黄油和煎饼(而不是面包)，同时还有一个根据唯一但完整的规则来翻煎饼的服务器。  
给你一栈的煎饼，请你编写一个程序用于指示这个栈如何被排序以使得最大的煎饼在最下面而最小的煎饼在最上面。  
煎饼的直径将被给出。  
栈中的所有煎饼的直径都不一样。  
对栈排序是通过一系列"翻转"来完成的。  
一次翻转的意思是：在两个煎饼之间插入铲子，然后将铲子上面的一堆煎饼整体翻过来。也就是指定一个位置，其上的子栈整体翻转。  
翻转的位置将会被给出。  
位置是这样定义的：栈底编号为1，栈顶编号为n  
一个栈的煎饼的给出方式，是从上到下给出煎饼的直径。  
举例来说，这是三个栈，左边的栈的最上面的煎饼直径为8  
8             7             2  
4             6             5  
6             4             8  
7             8             4  
5             5             6  
2             2             7  
左侧栈，可在位置3（即直径7）处翻转，得到中间的那个栈，而中间那个栈可在位置1（即直径2）处翻转，得到右侧的栈。

### Input ###

输入由多个煎饼栈组成。每个栈有1到30个煎饼，每个煎饼的直径在1-100之间。以文档结束为输入结束。每个栈，独占一行，从左到右依次代表从栈顶到栈底的煎饼的直径，空格隔开。

### Output ###

对于每个煎饼栈，输出首先应原样将栈的数据打印成一行。  
随后的一行是翻转位置的次序，空格隔开，以0结束。（结束的目标是最大直径在最下面，最小直径在最上面）。

### Sample Input ###

> 1 2 3 4 5  
> 5 4 3 2 1  
> 5 1 2 3 4

### Sample Output ###

> 1 2 3 4 5  
> 0  
> 5 4 3 2 1  
> 1 0  
> 5 1 2 3 4  
> 1 2 0

## 分析 ##

题目要求可以简化为，输入一组数，按照从小到大排列。排序时，只能进行前n个数全部翻转。输出原样数据，随后的一行是翻转位置的次序，空格隔开，以0结束。  
思路：可以每次把最大的数放到最后一个。把最大的数放到最后一个之后，这个数就排好了，接着排前面的数，有一点类似于冒泡排序。如果前面的数比后面的数大，就先把这个数及前面的数全部翻转，即把大数翻到最前面，然后再翻转一次，把大数翻转到没排好的最后一个位置。

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    
    public class Main { 
    	public static void main(String[] args) { 
    		Scanner s = new Scanner(System.in);
    		while (s.hasNextLine()) { 
    			String str = s.nextLine();
    			System.out.println(str);
    			String[] numStr = str.split(" ");
    			int sum = numStr.length;
    			ArrayList<Integer> num = new ArrayList<Integer>();
    			for (int i = 0; i < numStr.length; i++) { 
    				num.add(Integer.parseInt(numStr[i]));
    			}
    			ArrayList<Integer> temp = new ArrayList<Integer>(num);
    			Collections.sort(temp);
    			Collections.reverse(temp);
    			int end = sum - 1;
    			for (Integer integer : temp) { 
    				int index = num.indexOf(integer);
    				if (end == 0) { 
    					break;
    				}
    				if (end == index) { 
    					end--;
    					continue;
    				} else { 
    					if (index != 0) { 
    						for (int i = 0; i < (index + 1) / 2; i++) { 
    							Collections.swap(num, i, index - i);
    						}
    						System.out.print(sum - index + " ");
    					}
    					for (int i = 0; i < (end + 1) / 2; i++) { 
    						Collections.swap(num, i, end - i);
    					}
    					System.out.print(sum - end + " ");
    					end--;
    				}
    			}
    			System.out.println(0);
    		}
    	}
    }

英文原题  
Stacks and Queues are often considered the bread and butter of data structures and find use in architecture, parsing, operating systems, and discrete event simulation. Stacks are also important in the  
theory of formal languages.  
This problem involves both butter and sustenance in the form of pancakes rather than bread in  
addition to a finicky server who flips pancakes according to a unique, but complete set of rules.  
Given a stack of pancakes, you are to write a program that indicates how the stack can be sorted  
so that the largest pancake is on the bottom and the smallest pancake is on the top. The size of a  
pancake is given by the pancake’s diameter. All pancakes in a stack have different diameters.  
Sorting a stack is done by a sequence of pancake “flips”. A flip consists of inserting a spatula  
between two pancakes in a stack and flipping (reversing) all the pancakes on the spatula (reversing the  
sub-stack). A flip is specified by giving the position of the pancake on the bottom of the sub-stack to  
be flipped (relative to the whole stack). The pancake on the bottom of the whole stack has position 1  
and the pancake on the top of a stack of n pancakes has position n.  
A stack is specified by giving the diameter of each pancake in the stack in the order in which the  
pancakes appear.  
For example, consider the three stacks of pancakes below (in which pancake 8 is the top-most  
pancake of the left stack):  
8 7 2  
4 6 5  
6 4 8  
7 8 4  
5 5 6  
2 2 7  
The stack on the left can be transformed to the stack in the middle via flip(3). The middle stack can  
be transformed into the right stack via the command flip(1).  
Input  
The input consists of a sequence of stacks of pancakes. Each stack will consist of between 1 and 30  
pancakes and each pancake will have an integer diameter between 1 and 100. The input is terminated  
by end-of-file. Each stack is given as a single line of input with the top pancake on a stack appearing  
first on a line, the bottom pancake appearing last, and all pancakes separated by a space.  
Output  
For each stack of pancakes, the output should echo the original stack on one line, followed by some  
sequence of flips that results in the stack of pancakes being sorted so that the largest diameter pancake  
is on the bottom and the smallest on top. For each stack the sequence of flips should be terminated by  
a ‘0’ (indicating no more flips necessary). Once a stack is sorted, no more flips should be made.  
Sample Input  
1 2 3 4 5  
5 4 3 2 1  
5 1 2 3 4  
Sample Output  
1 2 3 4 5  
0  
5 4 3 2 1  
1 0  
5 1 2 3 4  
1 2 0