Uva 120 Stacks of Flapjacks

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=56

题目描述：给出a[1...n]和一种flip，每次flip允许对a[1...x]的位置进行反转（a[x]=a[1]...），问得到升序的反转方法。

首先是输入：gets读入一行，得到a[]

其次是离散化：并没有给出是1...n排列的条件，a[]可能不连续，需要离散化

然后是如何反转：因为n<=30，复杂度要求不高，可以考虑从后往前排，即先把最大的放在最后，然后依次把第二大...最小的放到对应的位置即可

// 22::19
# include <stdio.h>
# include <string.h>
# include <stdlib.h>

int n;
char s[3500];
int a[35];
int r[35];

int main()
{
    while (gets(s) != NULL) {
        puts(s);
        n = 0;
        char *p = s;
        while (sscanf(p, "%d", &a[n++]) != EOF) {
            for ( ; *p && (*p) != ' '; ++p) ;
            if (!*p) break;
            else ++p;
        }
        for (int i = 0; i < n; ++i) r[i] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (a[i] < a[j]) ++r[j];
                else ++r[i];
            }
        }
        int target = n-1;
        int i;
        while (target > 0) {
            for (i = 0; i < n; ++i) {if (r[i] == target) break; }
            if (target != i) {
                if (i != 0)  {
                    printf("%d ", n-i);
                    int mid = (i+1)/2;
                    for (int k = 0; k < mid; ++k) {
                        int tmp = r[k];
                        r[k] = r[i-k];
                        r[i-k] = tmp;
                    }
                }
                printf("%d ", n-target);
                int mid = (target+1)/2;
                for (int k = 0; k < mid; ++k) {
                    int tmp = r[k];
                    r[k] = r[target-k];
                    r[target-k] = tmp;
                }
            }
            --target;
        }
        printf("0
");
    }
    
    return 0;
}