uva 120 Stacks of Flap jacks
题意 翻转烧饼 每次翻转是从自选中的烧饼往上到顶部一整叠一起翻转 最终要得到从小到大排列的烧饼
解法 把烧饼从大到小每一个都进行一次判断,如果不在该放置的位置,就把这烧饼翻到顶,再翻到底,直到每个烧饼都判断完成。
代码:
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; #include <algorithm> int stack[105], t; int num[105]; char c; void tra(int k) { for (int i = 0; i < k/2; i ++) { int sb = stack[i]; stack[i] = stack[k - 1 - i]; stack[k - 1 - i] = sb; } } int findmax(int k) { int max; max = stack[k - 1]; for (int i = k - 1; i >= 0; i --) { if (stack[i] > max) max = stack[i]; } for (int i = k - 1; i >= 0; i --) { if (max == stack[i]) return i; } } int judge(int t) { for (int i = 0; i < t - 1; i ++) { if(stack[i] > stack[i + 1]) return 1; } return 0; } int main() { t = 0; memset(stack, 0, sizeof(stack)); while (scanf("%d%c", &stack[t], &c) != EOF) { t ++; if (c == '\n') { for (int i = 0; i < t - 1; i ++) { printf("%d ", stack[i]); } printf("%d\n", stack[t - 1]); int j = 0; int k = t; while (judge(t)) { if(findmax(k) == 0 && findmax(k) != k - 1) { num[j++] = t - k + 1; tra(k); } if(findmax(k) != 0 && findmax(k) != k - 1) { num[j++] = t - findmax(k); tra(findmax(k) + 1); num[j++] = t - k + 1; tra(k); } k --; } num[j] = 0; for(int i = 0; i < j; i ++) { printf("%d ",num[i]); } printf("%d\n", num[j]); t = 0; memset(num, 0, sizeof(num)); memset(stack, 0, sizeof(stack)); } } return 0; }