首页 > 代码库 > Poj 2499 Binary Tree
Poj 2499 Binary Tree
题目链接：http://poj.org/problem?id=2499
思路：
结点向左边移动时结点（a, b）变为( a+b, b),向右边移动时( a, b )变为( a, a + b);
为求最短路径<a1, a2, a3,...,an>，考虑从已经知道的结点(a, b)开始找出最短路径回到根节点(1, 1)；
即向左移动次数和向右移动次数最少回到根节点，由贪心算法，若 a>b 时，a 减少最大即减去 b；
若 a < b，b 减少最大即减去a值,循环直到到达根节点(1, 1)。
代码如下：
#include <iostream>using namespace std;int main(){ int n; scanf( "%d", &n ); for ( int i = 0; i < n; ++i ) { int a, b; int l, r; scanf("%d %d", &a, &b ); l = r = 0; while( a != 1 || b!= 1 ) { if ( a == 1) { r += b - a; b = 1; } else if ( b == 1 ) { l += a - 1; a = 1; } else if ( a > b ) { l += a / b; a -= b * ( a / b ); } else if ( a < b ) { r += b / a; b -= a *( b / a ); } } printf( "Scenario #%d:\n%d %d\n\n", i + 1, l, r ); } return 0;}
Poj 2499 Binary Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。