2019年蓝桥杯练习5-翻煎饼

2019年蓝桥杯练习5-翻煎饼

每周一题之5 翻煎饼
PC/UVa IDs: 110402/120,
Popularity: B, Success rate:high Level: 2
测试地址：
https://vjudge.net/problem/UVA-120

[问题描述] （翻译仅供参考）

Stacks and Queues are often considered the bread andbutter of data structures and find use in architecture, parsing,operating systems, and discrete event simulation.Stacks are also important in thetheory of formal languages.
堆栈和队列通常被认为是数据结构的面包和黄油，可用于体系结构、解析，操作系统和离散事件模拟。堆栈在形式语言理论中也很重要。
This problem involves both butter and sustenance inthe form of pancakes rather than bread in addition to a finicky server who flips pancakesaccording to a unique, but complete set of rules.
现在的问题涉及黄油和煎饼(而不是面包)，同时还有一个根据唯一但完整的规则来翻煎饼的服务器。
Given a stack of pancakes, you are to write a programthat indicates how the stack can be sorted so that the largest pancake is on the bottom and thesmallest pancake is on the top.
给你一栈的煎饼，请你编写一个程序用于指示这个栈如何被排序以使得最大的煎饼在最下面而最小的煎饼在最上面。
The size of a pancake is given by the pancake’sdiameter.
煎饼的直径将被给出。
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 twopancakes in a stack and flipping (reversing) all the pancakes on thespatula (reversing the sub-stack).
一次翻转的意思是：在两个煎饼之间插入铲子，然后将铲子上面的一堆煎饼整体翻过来。也就是指定一个位置，其上的子栈整体翻转。
A flip is specified by giving the position of thepancake on the bottom of the sub-stack to be flipped (relative to the whole stack).
翻转的位置将会被给出。
The pancake on the bottom of the whole stack hasposition 1
and the pancake on the top of a stack of n pancakeshas position n.
位置是这样定义的：栈底编号为1，栈顶编号为n
A stack is specified by giving the diameter of eachpancake in the stack in the order in which the pancakes appear.
一个栈的煎饼的给出方式，是从上到下给出煎饼的直径。
For example, consider the three stacks of pancakesbelow (in which pancake 8 is the top-most pancake of the left stack):
举例来说，这是三个栈，左边的栈的最上面的煎饼直径为8
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 stackin the middle via flip(3). The middle stack can be transformed into the right stack via the commandflip(1).
左侧栈，可在位置3（即直径7）处翻转，得到中间的那个栈，而中间那个栈可在位置1（即直径2）处翻转，得到右侧的栈。

Input（输入）

The input consists of a sequence of stacks ofpancakes. Each stack will consist of between 1 and 30 pancakes and each pancake will have an integerdiameter between 1 and 100. The input is terminated by end-of-file. Each stack is given as a single lineof 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.
输入由多个煎饼栈组成。每个栈有1到30个煎饼，每个煎饼的直径在1-100之间。以文档结束为输入结束。每个栈，独占一行，从左到右依次代表从栈顶到栈底的煎饼的直径，空格隔开。

Output（输出）

For each stack of pancakes, the output should echo theoriginal stack on one line, followed by some sequence of flips that results in the stack ofpancakes being sorted so that the largest diameter pancake is on the bottom and the smallest on top. For eachstack the sequence of flips should be terminated by a ‘0’ (indicating no more flips necessary). Once astack is sorted, no more flips should be made.
对于每个煎饼栈，输出首先应原样将栈的数据打印成一行。
随后的一行是翻转位置的次序，空格隔开，以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

题目解析

这一题大致意思是通过翻转（有一定要求，从翻转的地方往上，整个的翻转）来对一组数进行排序，然后输出每次翻转的位置。

• 由于最开始对题目理解错了，只是把最大值翻到了最下面，最小值翻到了最上面，中间就没有排序，以下是实现这种情况的代码：
  （这里使用了栈，目的是更形象的表示题目的翻转过程）

用栈来翻转时，先将需要翻转的出栈，并存到一个临时数组中，然后按出栈的顺序入栈，即先出栈的先入栈，后出栈的后入栈，这样就可以实现翻转了。

/*说明：以下代码实现的功能与原题有些偏差，实现的是将一堆煎饼中直径最大的翻到最下面，将 直径最小的翻到最上面，中间的煎饼没有排序。*/
#include<stdio.h>
#define Stack_Size 31
#define SIZE 31
typedef struct
{
   
	int elem[100];
	int top;
}SeqStack;
//初始化 
void InitStack(SeqStack *S)
{
      //构造一个空栈S 
	S->top=-1;
}
//进栈
int Push(SeqStack *S,int x)
{
   
 	if(S->top==Stack_Size-1) return 0;  //栈已满
	S->top++;
	S->elem[S->top]=x;
	return 1;	
} 
//出栈
int Pop(SeqStack *S,int x)
{
   
	if(S->top==-1)
	    return 0;
    else {
   
    	x=S->elem[S->top];
		S->top--;
		return x; 
	}
}  
void filp(int top,int bottom,SeqStack *S)    //实现翻转 
{
   
	int tmp[SIZE];
	int t=top;
	for(int i=top;i>=bottom;i--) {
       //将从top到bottom的元素出栈 
		tmp[i]=Pop(S,top);
		while(i==bottom) {
     //出栈完毕 
			Push(S,tmp[t]);   //将出栈的元素按出栈的顺序重新入栈 
			t--;
			if(t==bottom) {
     //将最大值入栈 
				Push(S,tmp[bottom]);
				break;
			}
		}
	}
}
void findmin(int top,SeqStack *S)   //找最小值 
{
   
	int min=101,mini; 
	int tmp[SIZE];
	for(int i=top;i>=1;i--) {
      //找最小值 
		tmp[i]=Pop(S,top);
		if(tmp[i]<min) {
   
			min=tmp[i];
			mini=i;
		}
	}
	if(mini==top) printf("0\n");
	else printf("%d 0\n",mini);
}
void deal(int data[SIZE],int len)   //处理
{
   
	SeqStack S;
	InitStack(&S);  //初始化栈
	int max=0,maxi;
	for(int i=len;i>=1;i--) {
     //将数组元素入栈 
		Push(&S,data[i]);
		if(data[i]>max) {
     //在入栈的时候顺便找最大值的位置 
			max=data[i];
			maxi=len-i+1;  //记录下标 
		}
	}
	if(maxi==1) {
     //如果最大值在栈底 
		findmin(len,&S);   //找最小值 
	} 
	else if(maxi==len) {
     //如果最大值在栈顶 
		printf("1 ");    //从栈底翻 
		filp(len,1,&S);    //将最大值翻到最下面 
		findmin(len,&S);   //找最小值 
	}
	else {
   
		printf("%d ",maxi);
		filp(len,maxi,&S);   //将最大值翻到最上面 
		printf("1 ");
		filp(len,1,&S);    //将最大值翻到最下面 
		findmin(len,&S);   //找最小值 
	} 
}
int main()
{
   
	int sc[SIZE];
	int n=1;
	while(scanf("%d",&sc[n])!=EOF) {
   
		while(getchar()!='\n') {
   
			n++;
			scanf("%d",&sc[n]);
		}
		for(int i=1;i<=n;i++)  
		    printf("%d ",sc[i]);
		printf("\n"); 
		deal(sc,n);
		n=1;
	}
	return 0;
} 

以下的代码是通过了在线测试的：（排序的思想主要是每次都找最大值，先将最大值翻到顶部，然后再从最下面翻，把最大值翻到最下面。当然，这个过程中需要考虑到一些特殊情况，比如最大值在底部和顶部时，处理方式有细微的差别，注意判断。）

• 这里有一个简单的分析图演示了一下寻找的过程：
  

/*由于对结构体和栈的使用不是很会，下面的代码使用了比较多的入栈和出栈操作*/
#include<stdio.h>
#define Stack_Size 31
#define SIZE 31
typedef struct
{
   
	int elem[100];
	int top;
}SeqStack;
//初始化 
void InitStack(SeqStack *S)
{
      //构造一个空栈S 
	S->top=-1;
}
//进栈
int Push(SeqStack *S,int x)
{
   
 	if(S->top==Stack_Size-1) return 0;  //栈已满
	S->top++;
	S->elem[S->top]=x;
	return 1;	
} 
//出栈
int Pop(SeqStack *S,int x)
{
   
	if(S->top==-1)
	    return 0;
    else {
   
    	x=S->elem[S->top];
		S->top--;
		return x; 
	}
}  
void filp(int top,int bottom,SeqStack *S)    //实现翻转 
{
   
	int tmp[SIZE];
	int t=top;
	for(int i=top;i>=bottom;i--) {
       //将从top到bottom的元素出栈 
		tmp[i]=Pop(S,top);
		while(i==bottom) {
     //出栈完毕 
			Push(S,tmp[t]);   //将出栈的元素按出栈的顺序重新入栈 
			t--;
			if(t==bottom) {
     //将最大值入栈 
				Push(S,tmp[bottom]);
				break;
			}
		}
	}
}
int findMaxi(int top,int bottom,SeqStack *S)   //找最大值的位置 
{
   
	int tmp[SIZE];
	int max=0,maxi;
    for(int i=top;i>=bottom;i--) {
      //将栈中的元素依次出栈，在出栈的过程中记录下最大值及其位置 
    	tmp[i]=Pop(S,top);
    	if(tmp[i]>max) {
   
    		max=tmp[i];
    		maxi=i;
		}
	}
	for(int j=bottom;j<=top;j++) {
     //把元素重新入栈，恢复 
		Push(S,tmp[j]);
	}
	return maxi;
}
void deal(int top,int bottom,SeqStack *S)
{
   
	int maxi=findMaxi(top,bottom,S);
    while(1) {
    
		if(top==bottom) {
     //找完了 
			printf("0 \n");
			break;
		}   
  		if(maxi==bottom) {
    //在栈底
  			bottom++;   //继续往上找 
			maxi=findMaxi(top,bottom,S);
        } else if(maxi==top){
     //在栈顶 
        	printf("%d ",bottom);
        	filp(top,bottom,S);
        	bottom++;   //继续往上找 
			maxi=findMaxi(top,bottom,S);
		} else {
         //不在栈底和栈顶 
			printf("%d ",maxi);
			filp(top,maxi,S);
			printf("%d ",bottom);
        	filp(top,bottom,S);
       		bottom++;   //继续往上找 
			maxi=findMaxi(top,bottom,S);
		}
	}
}
int main()
{
   
	int sc[SIZE];
	int top=1;
	while(scanf("%d",&sc[top])!=EOF) {
   
		while(getchar()!='\n') {
   
			top++;
			scanf("%d",&sc[top]);
		}
		for(int i=1;i<=top;i++)  printf("%d ",sc[i]);
		printf("\n"); 
		//下面开始处理 
		SeqStack S;
		InitStack(&S);  //初始化栈
		int max=0,maxi;
		for(int i=top;i>=1;i--) {
     //将数组元素入栈 
			Push(&S,sc[i]);
		}
		deal(top,1,&S);
		top=1;
	}
	return 0;
} 

• 下面也给出一个使用Java代码实现的：（代码来自： 蓝桥学苑 第5周“翻煎饼”饭补，请领取~）

import java.util.Arrays;
import java.util.Scanner;

public class W5 {
   
	public static void main(String[] args) {
   
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
   
			String line = sc.nextLine();
			String[] data_str = line.split(" ");
			int[] data = new int[data_str.length];
			int i = 0;
			for (String d : data_str) {
   
				data[i++] = Integer.parseInt(d);
			}
			// 接收完一行，立即输出
			System.out.println(line);
			// 处理数组
			deal(data);
		}
	}
	private static void deal(int[] data) {
   
		int len = data.length;
		// 有序的数组
		int[] target = new int[len];
		System.arraycopy(data, 0, target, 0, len);
		Arrays.sort(target);
		// 定位一个下标，初始值为len-1，即目标栈的最末一个元素
		// 目标是把这个值在原始栈中通过翻转到达p位置，即归位
		int p = len - 1;
		// 从大到小依次归位
		while (p > 0) {
   
			// 找到target[p]在原始数组中的位置
			int i = indexOf(data, target[p]);
			if (i == p) {
   
				p--;
				continue;
			}
			if (i > 0) {
   
				// 1. 把它翻到顶上
				flip(data, len, len - i);
			}
			// 2. 再把它翻到p这个位置
			flip(data, len, len - p);
			p--;
		}
		System.out.println(0);
	}
	/** * * * * @param data * * @param key * * @return * */
	private static int indexOf(int[] data, int key) {
   
		for (int i = 0; i < data.length; i++) {
   
			if (data[i] == key)
				return i;
		}
		return -1;
	}
	/** * * 在位置i对data数组进行翻转(reverse) * * @param data * * @param k * */
	private static void flip(int[] data, int len, int k) {
   
		System.out.print(k + " ");
		int begin = 0;
		int end = len - k;
		// 两个指针往中间走，两两互换
		while (begin < end) {
   
			data[begin] ^= data[end];
			data[end] ^= data[begin];
			data[begin] ^= data[end];
			begin++;
			end--;
		}
	}
}