《算法竞赛入门经典》之"算法设计与优化策略" - csgc0131123 - 博客园
给你一叠薄煎饼，请你写一个程序来指出要如何安排才能使这些薄煎饼由上到下依薄煎饼的半径由小到大排好。所有的薄煎饼半径均不相同。要把薄煎饼排好序需要对这些薄煎饼做翻面（flip）的动作。方法是以一抹刀插入一叠薄煎饼中，然后做翻面的动作（也就是说在抹刀上面的薄煎饼经翻 面后，会依相反的次序排列）。若一叠共有n个薄煎饼，我们定义最底下的薄煎饼的位置为1，最上面的薄煎饼位置为n。当抹刀插入位置为k时，代表从位置k到 位置n的薄煎饼要做翻面的动作。一开始时，这叠薄煎饼随意堆放，并以半径大小来表示。
大意就是按照题目所给的方法排序并输出排序的过程。
题目的排序方法就是每次可以任意选个地方然后从头开始到这个地方翻转一下，
题目中的编号是逆序的即第一个为n最后一个为1
如5 1 2 3 4
先选取第一个就是从4到开头翻转变为4 3 2 1 5然后选第二个1然后翻转下1 2 3 4 5.
类似于选择排序，每次把要排的那个数字先翻转到开头，然后选择末尾第一个未排序的翻转，这样这个元素就排好位置了。
实现过程就是每次找到当前最大的元素，如果他在排完序后的位置则不用排序，否则翻转到开头然后翻转到他排完序后的位置，因为是每次排当前最大的所以排完序后的位置我们是知道第一次在n，第二次在n-1一次类推。
Read full article from 《算法竞赛入门经典》之"算法设计与优化策略" - csgc0131123 - 博客园
No comments:
Post a Comment