第五章 二叉树 练习题(数据结构与算法MOOC)

9.题目

倒着思考，注意超时处理

代码：

#include<iostream>
#include<stdio.h>
using namespace std;


int main()
{
	int t,cas=0;
	cin >> t;
	while (t--)
	{
		cas++;
		long long a, b;
		int l, r;
		cin >> a >> b;

		l = 0; r = 0;
		while (a != 1 || b != 1)
		{
		    if (a == 1) { r += b - 1; b = 1; }
			else if (b == 1) { l += a - 1; a = 1; }
			else 
			{
				if (a > b)
				{
					int c = a / b;
					if (c > 1) {
						a = a - c*b;
						l += c;
					}
					else
					{
						l++;
						a -= b;
					}
				}
				else
				{
					int c = b / a;
					if (c > 1)
					{
						b = b - c*a;
						r += c;
					}
					else
					{
						r++;
						b -= a;
					}
				}
			}
			
		}
		
		printf("%s%d:\n", "Scenario #", cas);
		cout << l << " " << r << endl<<endl;

	}
}#include<iostream