题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=56
解题:题目要求的是设计一种这样的方法使得可以完成这样的要求,一开始我看成了最小次数的操作序列,这样一来就只有选择迭代加深搜索了。。。
然而这题只是要求达到最终的效果,因此难度大大降低。
只要从大到小来排就行了,因为最大的肯定在最后面,后序操作不会影响到它。另外注意到对于尚未在最终位置的数最大两次就可以将它放置到应该在的位置。。。。
//
// main.cpp
// uva 120 - Stacks of Flapjacks
//
// Created by XD on 15/8/12.
// Copyright (c) 2015年 XD. All rights reserved.
//
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <string.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cstdio>
using namespace std ;
int original[30] ;
int n ;
int sorted[30] ;
int pos[110] ;
char s[10100] ;
void getOriginal()
{
int len = (int ) strlen(s) ;
n = 1 ;
for (int i = 0; i < len; i++) {
int num = 0 ;
if (s[i] != ' ') {
while (i < len && s[i]!=' ') {
num = num * 10 + s[i] - '0' ;
i++ ;
}
pos[num] = n ;
sorted[n] = num ;
original[n++] = num ;
}
}
}
void flip(int x)
{
int i = 1 ;
while (i < x) {
pos[original[x]] = i ;
pos[original[i]] = x ;
int temp = original[x] ;
original[x] = original[i] ;
original[i] = temp ;
i++ ; x-- ;
}
}
void flips()
{
for(int i = n-1 ; i > 0 ;i--)
{
if (pos[sorted[i]] == i) {
continue ;
}
else if (pos[sorted[i]]==1)
{
printf("%d " ,n-i) ;
flip(i) ;
}
else {
printf("%d " ,n - pos[sorted[i]]) ;
flip(pos[sorted[i]]) ;
printf("%d " , n-i) ;
flip(i) ;
}
}
printf("0\n") ;
}
int main() {
while (gets(s)!=NULL) {
puts(s) ;
getOriginal() ;
sort(sorted+1, sorted+n) ;
flips() ;
} return 0;
}