8-1 Stacks of Flapjacks UVA120

题意：有一叠煎饼在锅里 n n<=30张每张都有一个数字代表它的大小厨师每次可以选择一个数k 把从锅底开始数第k张上面的煎饼全部反过来即原来的在上面的煎饼现在到了下面如

Sample Input

1 2 3 4 5

5 4 3 2 1

5 1 2 3 4

Sample Output

1 2 3 4 5

5 4 3 2 1

1 0

5 1 2 3 4

1 2 0

按照选择排序模拟

各种加一减一模拟的好乱糟糕的代码

#include<bits/stdc++.h>
using namespace std;
#define  N 30
int a[N];
int path[N];
int n,c;

void chang(int x)
{
    int temp[N];
    for(int i=1;i<=n-x+1;i++)
           temp[i]=a[n-x-i+2];
    for(int i=n-x+2;i<=n;i++)
        temp[i]=a[i];
    memcpy(a,temp,sizeof a);
}

void dfs(int cur)
{
    if(cur==1)
    {
       for(int i=0;i<c;i++)
          printf("%d ",path[i]);
          printf("0
");
          return ;
    }
    int maxx=0;
    int u=0;
    for(int i=1;i<=cur;i++)
        {
            if(a[i]>maxx){maxx=a[i],u=i;   }
        }
    if(u!=cur)
    {
          if(u!=1)
            chang(n-u+1);path[c++]=n-u+1;
            chang(n-cur+1);path[c++]=n-cur+1;
    }
    dfs(cur-1);
}

int main()
{
   char s[1000];
   while(fgets(s,1000,stdin))
   {
       int cnt=1;
       int v=0;
       int i=0;
       while(i<strlen(s))
       {
           while(!isspace(s[i])&&i<strlen(s))v=v*10+s[i++]-'0';
           a[cnt++]=v;
           v=0;
           i++;
       }

     n=cnt-1;
     for(int i=1;i<=n;i++)
     {

         printf("%d",a[i]);
         if(i!=cnt)printf(" ");
     }
     printf("
");
     c=0;
     dfs(n);
   }
}

数据读入用流来写很快！！！还有找最大值下标函数！！交换的话直接一个循环加swap函数不用temp

我写了70行 lrj大大写了30行

菜鸡还需努力。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 30 + 5;
int n, a[maxn];

// 翻转a[0..p]
void flip(int p) {
  for(int i = 0; i < p-i; i++)
    swap(a[i], a[p-i]);
  printf("%d ", n-p);
}

int main() {
  string s;
  while(getline(cin, s)) {
    cout << s << "
";
    stringstream ss(s);
    n = 0;
    while(ss >> a[n]) n++;
    for(int i = n-1; i > 0; i--) {
      int p = max_element(a, a+i+1) - a; // 元素a[0..i]中的最大元素
      if(p == i) continue;
      if(p > 0) flip(p); // flip(0)没啥意思，是不？
      flip(i);
    }
    printf("0
");
  }
  return 0;
}

相关推荐