首页 > 代码库 > UVa120 Stacks of Flapjacks (构造法)
UVa120 Stacks of Flapjacks (构造法)
链接：http://vjudge.net/problem/18284
分析：摊煎饼问题。以从大到小的顺序依次把每个数排到正确的位置，比如当处理第i大的煎饼时，是不会影响到第1,2,3，...，i-1大的煎饼的（它们已经正确的翻到了煎饼堆底部的i-1个位置上），翻煎饼的方法是先翻到最上面，然后翻到正确的位置，翻好了以后煎饼堆底部i个位置上的煎饼都已经正确放好就不用管了，接下来就是找第i+1大的煎饼放到下数上第i+1个位置上，不过对于当前最大煎饼的位置要分类讨论，如果已经在其正确位置上就什么也不用做，如果在最顶上，就只需翻一次到正确位置上，否则先翻到最顶上然后再翻到正确位置。
1 #include <string> 2 #include <iostream> 3 #include <sstream> 4 using namespace std; 5 6 const int maxn = 30 + 5; 7 8 int n, a[maxn]; 9 10 void flip(int p) {11 for (int i = 0; i < p - i; i++)12 swap(a[i], a[p - i]);13 printf("%d ", n - p);14 }15 16 int main() {17 string s;18 while (getline(cin, s)) {19 cout << s << endl;20 stringstream ss(s);21 n = 0;22 while (ss >> a[n]) n++;23 for (int i = n - 1; i > 0; i--) {24 int maxv = a[i], index = i;25 for (int j = i - 1; j >= 0; j--)26 if (a[j] > maxv) {27 maxv = a[j];28 index = j;29 }30 if (index == i) continue;31 if (index > 0) flip(index);32 flip(i);33 }34 printf("0\n");35 }36 return 0;37 }
UVa120 Stacks of Flapjacks (构造法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。