首页 > 代码库 > Uva120 Stacks of Flapjacks
Uva120 Stacks of Flapjacks
题意:
给你一串数字,你可以选择一个位置,将这个位置以上的数字全部翻转过来。问怎么翻转才能把大的放在下面,小的放上面。
题解:
先用另一个数组保存最后的结果(大的在下,小的在上,sort一下就好)。然后从最后一个位开始匹配。如果当前位置的数和最后结果不一样,就要把它翻到这里。
就要在数组里面找到这一个数,先把他翻到最上面,在翻一下就可以到需要的位置了。
例子:
4 5 2
3 3 1
5 -> 4 -> 4
1 1 3
2 2 5
我们一开始最下面需要放5。先把5翻到最上面,在翻一下就可以到最下面了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <string> 6 #include <vector> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <sstream> 11 #include <algorithm> 12 using namespace std; 13 #define pb push_back 14 #define mp make_pair 15 #define ms(a, b) memset((a), (b), sizeof(a)) 16 //#define LOCAL 17 #define eps 0.0000001 18 typedef long long LL; 19 const int inf = 0x3f3f3f3f; 20 const LL INF = 0x7fffffff; 21 const int maxn = 100+10; 22 const int mod = 1000000007; 23 int num[maxn]; 24 int wei[maxn]; 25 void sw(int x) 26 { 27 int t; 28 for(int i=0;i<=x/2;i++) 29 { 30 t = wei[i]; 31 wei[i] = wei[x-i]; 32 wei[x-i] = t; 33 } 34 } 35 void findd(int x, int n,int p){ 36 int i; 37 for(i=0;i<n;i++){ 38 if(wei[i] == x){ 39 break; 40 } 41 } 42 if(i!=0){ 43 printf("%d ", p-i+1); 44 sw(i); 45 } 46 } 47 int main() { 48 #ifdef LOCAL 49 freopen("jumping.in", "r", stdin); 50 // freopen("output.txt", "w", stdout); 51 #endif // LOCAL 52 int hh, p=0; 53 char c; 54 while(~scanf("%d%c", &hh, &c)){//每次读入2个 55 num[p] = hh; 56 wei[p] = hh; 57 if(c == ‘\n‘){//一行结束 58 for(int i = 0;i<=p;i++){//一开始需要打印一次 59 if(i==0) printf("%d", num[i]); 60 else printf(" %d", num[i]); 61 } 62 printf("\n"); 63 sort(num, num+p+1)//排序一下,得到结果 64 for(int i=0;i<=p;i++){//从最后一个开始 65 if(num[p-i]!=wei[p-i]){//如果当前位置和最后答案要求不一样 66 findd(num[p-i], p-i, p);//在[0, p-i]内找到num[p-i](最后答案),并且交换到最上面 67 sw(p-i);//交换 68 printf("%d ", i+1);//打印交换位置 69 } 70 } 71 printf("0\n"); 72 p = 0; 73 } 74 else 75 p++; 76 } 77 return 0; 78 }
Uva120 Stacks of Flapjacks
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。