【uva 120】Stacks of Flapjacks（算法效率--构造法+选择排序思想）

题意：有N张正在锅里的一叠煎饼，每张都有一个数字，代表其大小。厨师每次可以选择一个数k，把从锅底开始数第k张上面的煎饼全部翻过来，即原来在上面的煎饼现在到了下面。要求设计一种方法使得所有煎饼按照从小到大排序（最上面的煎饼最小）。

解法：基本操作就是颠倒一个连续子序列。既然没有限制什么其他的条件，就一个个完成好了。把最大的移到最上面，再移到最下面；再是第二大、第三大等等......

P.S.而我实在是太搞笑了！echo输入我直接忽略了。。自己打的比紫书上的标程长了将近一倍，还错了。。因此，要注意数据比较小，可以for一遍找第i大的就好了，别离散化什么的。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6

 7 int n;

 8 int a[35];

 9

10 int findmax(int x)

11 {

12     int p=1;

13     for (int i=x;i>1;i--)

14       if (a[i]>a[p]) p=i;

15     return p;

16 }

17 int sswap(int x,int y) {int t;t=a[x],a[x]=a[y],a[y]=t;}

18 void flip(int x)

19 {

20     for (int i=1;i<=x/2;i++) sswap(i,x-i+1);

21     printf("%d ",n-x+1);

22 }

23 int main()

24 {

25     while (scanf("%d",&a[1])!=EOF)

26     {

27       n=1;char ch;

28       while (1)

29       {

30         ch=getchar();

31         if (ch!=' ') break;

32         scanf("%d",&a[++n]);

33       }

34       for (int i=1;i<=n;i++) printf("%d ",a[i]);

35       printf("\n");

36       for (int i=n;i>1;i--)

37       {

38         int p=findmax(i);

39         if (p==i) continue;

40         if (p!=1) flip(p);

41         flip(i);

42       }

43       printf("0\n");

44     }

45     return 0;

46 }

巴特西

【uva 120】Stacks of Flapjacks（算法效率--构造法+选择排序思想）

最新文章

热门文章