【洛谷P1080国王游戏】2025-3-7

缘由洛谷P1080 国王游戏 wa一个点_编程语言-CSDN问答

用数据分析推导：左手按升序右手按升序计算即可，由于涉及大数乘法和除法，研究如何变换算法就显得有点意思了，可以把大整数转为整数范围内运算，玩推导就是个乐子，确实是个乐子。
积商不变性质，如：7*5*2/4=3*5*2/4+1*5*2=3*1*2/4+1*5*2+1*2*3=2/4+1*5*2+1*2*3+1=17.5，
7*4*2/7=0*4*2/7+1*2*4=8=1*4*2/1，4*2/4=0*2/4+1*2=2=1*2/1，
7*4*2/4=7*0*2/4+1*7*2=14=3*4*2/4+1*4*2=3*0*2/4+1*4*2+1*2*3=14。
如果看得懂的话，使用以上推导去做，可减小乘积的量，同时使用LONG LONG数据类型的话，对100的数据应该足够使用，免去编写大数运算，其实，已经解题了，且程序也变得更容易实现。

void 洛谷P1080国王游戏()
{
	int a[1080][3]{}, n = 0, j = 0, x = 0;
	bool k = 1; long long m = 0;
	std::cin >> n >> a[0][0] >> a[0][1];
sr:if (x++ < n)
{//3 1 1 2 3 7 4 4 6//4 1 1 2 3 7 4 4 6 7 7
	   std::cin >> a[x][0] >> a[x][1];
	   goto sr;
}
px:if (j < n)
{//左手右手升序
	   if (--x > j)
	   {
		   if (a[x][0] < a[x - 1][0])
			   两数交换(a[x][0], a[x - 1][0]), 两数交换(a[x][1], a[x - 1][1]), k = 0;
		   if (a[x][0] == a[x - 1][0] && a[x][1] < a[x - 1][1])
			   两数交换(a[x][0], a[x - 1][0]), 两数交换(a[x][1], a[x - 1][1]), k = 0;
		   if (x < n)
		   {
			   if (a[n - x][0] > a[n - x + 1][0])
				   两数交换(a[n - x][0], a[n - x + 1][0]), 两数交换(a[n - x][1], a[n - x + 1][1]), k = 0;
			   if (a[n - x][0] == a[n - x + 1][0] && a[n - x][1] > a[n - x + 1][1])
				   两数交换(a[n - x][0], a[n - x + 1][0]), 两数交换(a[n - x][1], a[n - x + 1][1]), k = 0;
		   }
	   }
	   if (x == j)
	   {
		   x = n - j;
		   if (k)j = n;
		   else ++j, k = 1;
	   }
	   goto px;
}
js:if (n)
{
	   if (a[--j][0] >= a[n][1])
	   {
		   a[j][2] = a[j][0] / a[n][1], a[j][0] %= a[n][1];
		   x = n;
	   qs:if (x--){ if (x != j)a[j][2] *= a[x][0]; goto qs; }
	   }
	   else if (a[j][0] < a[n][1])
	   {
		   if (j)
		   {
			   x = n;
		   qj:if (--x){ a[j - 1][0] *= a[x][0], a[x][0] = 1; goto qj; }
		   }
		   else goto sc;
	   }
	   if (a[j][0] == 0)
	   {
	   sc:if (x++ < n){ m += a[x][2]; goto sc; }
		   std::cout << m << "\n"; n = 0;
	   }
	   goto js;
}
}



px:if (j < n)
{//左手升序,右手降序
	if (--x > j)
	{
		if (a[x][0] < a[x - 1][0])
			两数交换(a[x][0], a[x - 1][0]), 两数交换(a[x][1], a[x - 1][1]), k = 0;
		if (a[x][0] == a[x - 1][0] && a[x][1] > a[x - 1][1])
			两数交换(a[x][0], a[x - 1][0]), 两数交换(a[x][1], a[x - 1][1]), k = 0;
		if (x < n)
		{
			if (a[n - x][0] > a[n - x + 1][0])
				两数交换(a[n - x][0], a[n - x + 1][0]), 两数交换(a[n - x][1], a[n - x + 1][1]), k = 0;
			if (a[n - x][0] == a[n - x + 1][0] && a[n - x][1] < a[n - x + 1][1])
				两数交换(a[n - x][0], a[n - x + 1][0]), 两数交换(a[n - x][1], a[n - x + 1][1]), k = 0;
		}
	}
	if (x == j)
	{
		x = n - j;
		if (k)j = n;
		else ++j, k = 1;
	}
	goto px;
}

 
可见对二维数组不同升降排序非常简便实现。

商不变性质：积是除数的倍数，a*b/c=c*n/c=n；如果a*b是c的倍数则商是倍数；如：7*4/4=7。
积商不变性质，变为加法运算：7/4=4/4+3/4=1+0.75，2*7/4=2*3/4+1*2=2/4+3=3.5，
2*5*7/4=2*7*（4/4+1/4）/4=1*2*7+2*7*1/4=14+2*（4/4+3/4）=14+2+2*3/4=16+2/4+1=17.5，
（2*5）*7/4=2*7+2*7/4=14+3+2/4=17.5，1*2*7+1*2*7/4=14+3+2/4=17.5，2*1*3/4+（1*2*7+1*2）=16+6/4=16+1+2/4=17.5，3*5*2/4+1*5*2=3*1*2/4+1*5*2+1*2*3=2/4+1*5*2+1*2*3+1=17.5。

不要说AI了，来个人证明我分析的分式乘法转加法运算是错的，有？这种推导不是书本上有的。
其实这道题目可以优化或可不用数组，结合我分析的转换，完全可以抛开大数运算，用数据范围内运算即可，如INT范围，只要把积控制在数据范围内最大不超时就转换。如：４＊５＊６／７＝１２０／７＝１７＋１／７由于题目取整，最后不能化整的分式不用运算，待空闲写下优化算法代码。