Uva120 Stacks of Flapjacks【构造法】【例题8-1】

题目： Stacks of Flapjacks

题意：给出一组数，将数按递增排序，排序规则：给出的数从左到右为从顶部到底部，每次选一个数k，代表从底部数第k个以上的煎饼都翻过来。按照规则排序，把每次的k值输出。

思路：由题可得每次都是0~k的翻转，所以我们可以从大到小依次将值翻转到0位置，然后按照逆序当前是倒数第k大的数就将是第k位置到0翻转，直达翻转到0位置即排序成功。

参考：紫书-例8-1-P236

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 35;int n,a[maxn],order[maxn];void read(string str){//将字符串转化为数字    int integer = 0;n = 0;    for(int i=0;str[i] != '/0';i++){        if(str[i] >= '0' && str[i] <= '9') integer = integer*10 + (str[i] - '0');        if(str[i] == ' ' && str[i+1] != ' '){            a[n++] = integer;            integer = 0;        }    }    a[n++] = integer;}void flip(int pos){//翻转煎饼    for(int i=0;i<=pos/2;i++){        int temp = a[i];        a[i] = a[pos - i];        a[pos - i] = temp;    }}void fun(){    memcpy(order,a,sizeof(a));    sort(order,order+n);    int cnt = n-1;//当前最大值的下标    while(cnt > 0){//将所有值操作完后下标到达了0        if(order[cnt] == a[cnt]) cnt--;//当前最大值就在底部就寻找下一个较大值        else{            int record;            for(int i=0;i<n;i++)                if(a[i] == order[cnt]) {record = i;break;}//寻找当前找的最大值的位置            if(record == 0){//当最大值在顶部时，直接交换后最大值将变为下一个                cout << n-cnt << " ";                flip(cnt);                cnt--;            }            else{//最大值不在顶部的话翻转到顶部，等下次再翻转                cout << n - record << " ";                flip(record);            }        }    }}int main(){    string str;    while(getline(cin,str)){        read(str);        cout << str << endl;        fun();        cout << "0" << endl;    }    return 0;}