B - Problem B-分可乐

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3
4 1 3
0 0 0
Sample Output
NO
3

我的见解：这条题看起来好像小时候倒酒的问题，因为100毫升，数据不大，一开始也没有考虑了用递归，毕竟创一个比较麻烦，但多次runtime，感觉有必要。。。
审题先，三个整数，如果平分出现小数是肯定分不了的，所以先将奇数输出NO；然后开始对偶数开始考虑，先从小的入手时间肯定长，所以先判断两个杯子的大小，让大的杯子是M，小的杯子是N，如果一样那肯定能平分啊，先将饮料倒满大的，大的又倒饮料瓶满小的，小的又倒回去原来饮料瓶，最后余下来的倒进小的，原来饮料瓶往大的里面倒装满，反复操作后剩下的就刚好是饮料瓶体积除去小的的余数，再从小的倒回来就好。但在做题过程中发现，如果是8 1 7就是一个循环 40 37 3是二个循环 70 9 61是四个循环所以用递归更方便，大概是按以上思路去倒，
我说这么多，好像也好难懂，那玩就画个图纸吧，，，，，，，，，，，，，，，，，，，
比如70 61 9这组要想平分就是两份35对吧，35最后肯定是由小的倒回去，35除以9余8，最后我只要让饮料瓶里只有8，那我的方法就可以轻松达成了平分可乐，，，
说也不好说看看图： B - Problem B-分可乐
按照原始方法代码如下：

#include <iostream>
using namespace std;


int main()
{
	int S, M, N, t, a, k;
	while (cin >> S >> M >> N)
	{
		if (S == 0 && M == 0 && N == 0)break;
		if ((S % 2) == 1)
		{
			cout << "NO" << endl;
			continue;
		}
		if (M < N)
		{
			t = M; M = N; N = t;
		}
		a = (S / 2 )% N;
		k = M % N;
		if (a != 0 && k == 0)
		{
			cout << "NO" << endl;
		}
		else if ((a == 0 && k == 0)||( a == 0 && k != 0))
		{
			cout << (1 + S / N-2*N) << endl;
		}
		else
		{
			int h = 3 + M / N * 3;
			for (int i = k; i > N-a; )
			{
				h += (M / N + 2) * 2;
				i -= N % k;
			}
			cout << h << endl;
		}
	}
}

然后因为超出时间限制，我优化了将其中合并
用辗转相除法求出大的和小的之间的最大公因数一，在去求饮料瓶和最大公因数一之间的最大公因数二，其实二和一是相等的，做题太紧张，没考虑这么多，
代码如下：

#include <iostream>
using namespace std;

int main()
{
    int S, M, N,t,a,k;
	while (cin >> S >> M >> N)
	{
		if (S == 0&&M==0&&N==0)break;
		if ((S % 2) == 1)cout << "NO" << endl;
		if (M < N)
		{
			t = M; M = N; N = t;
		}
		if (M%N == 0)a = N;
		else if (N % (M%N) == 0)a = M % N;
		else if (N % (N % (M%N)) == 0)a = (N % (M%N));
		else if (N % (N % (N % (M%N))) == 0)a = (N % (N % (M%N)));
		else a = (N % (N % (N % (M%N))));
		if (S%a == 0)S = S / a;
		else if (a % (S%a) == 0)S = S / (S%a);
		else S = S / (a % (S%a) == 0);

		if (S % 2)cout << "NO" << endl;
		else cout << S - 1 << endl;
	

	}
}

这次出现runtime了然后就再用了递归，听说有高级算法，毕竟初学，等学好运用高级算法再回来做一遍，

代码如下：

#include <iostream>
using namespace std;

int kk(int a, int b)
{
	if (a%b == 0)return b;
	else return kk(b, a%b);
}

int main()
{
    int S, M, N,t,a,k;
	while (cin >> S >> M >> N)
	{
		if (S == 0&&M==0&&N==0)break;
		if ((S % 2) == 1)
		{
			cout << "NO" << endl;
			continue;
		}
		if (M < N)
		{
			t = M; M = N; N = t;
		}
		k = kk(M, N);
		k= kk(S, k);         //优化 可省略这一步骤 因为两个数字的公因数是A，他们的和和这个公因数A的最大公因数也是A
		S = S / k - 1;
		if (((S+1) % 2) == 1)cout << "NO" << endl;
		else cout << S << endl;
	

	}
}

B - Problem B-分可乐

相关推荐