翻煎饼_简单模拟

翻煎饼_简单模拟_C++

一、题目描述（懒人可直接跳过看题目概述）

题目来源：

SWUST OJ 题目0254

http://acm.swust.edu.cn/problem/0254/

二、问题概述

　　给出一列数，每次可将包含首项的子序列翻转，也就是说从开头数若干个数字进行翻转

　　翻转操作具体如：1 2 3 4 5 → 5 4 3 2 1 ，直白来讲就是倒过来念

　　要求用最少的翻转次数后，使数列从小到大排列

三、问题分析

　　先找到最大的数，把它翻转到第一个，接着翻转整个数列把它置于最后一个，这样完成一次操作

　　最大的数已经置于末尾，那么之后的操作需要对它不造成影响，所以把数列数 -1，也就是丢下最后一个数不管了

　　然后我们处理剩下的 n-1 个数列，即处理子问题

　　这里容易出现一个错误，如果最大的数为第一个数，那么就不需要进行第一次翻转，此处需要特判一下

四、AC代码

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<algorithm>
 7 #define N 1001
 8 using namespace std;
 9 
10 int n,ans,a[N];
11 void change(int x)
12 {
13     int l,r;
14     ans++;
15     l=r=x/2;
16     r++;
17     if (x%2==1) r++;
18     while (l>0) swap(a[l--],a[r++]);
19 }
20 int main()
21 {
22     int i,k;
23     scanf("%d",&n);
24     for (i=1;i<=n;i++) scanf("%d",&a[i]);
25     ans=0;
26     while (n>1)
27     {
28         k=1;
29         for (i=2;i<=n;i++)
30         {
31             if (a[k]<a[i]) k=i;
32         }
33         if (k!=n)
34         {
35             if (k>1) change(k);
36             change(n);
37         }
38         n--;
39     }
40     printf("%d
",ans);
41     return 0;
42 }

提交结果

QQ：740929894