一、题目描述

1.1题干

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

1.2输入输出数据

输入：

第一行包含一个整数 n，表示大臣的人数。

第二行包含两个整数 a 和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出：

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

数据范围：

对于 20% 的数据，有 1≤n≤10,0<a,b<8；

对于 40% 的数据，有1≤n≤20,0<a,b<8；

对于 60% 的数据，有 1≤n≤100；

对于 60% 的数据，保证答案不超过 10 的9次方 ；

对于 100% 的数据，有 1≤n≤1,000,0<a,b<10000。

1.3题目链接

蓝桥杯该题链接：https://www.lanqiao.cn/problems/391/learning/?page=1&first_category_id=1&tag_relation=intersection&problem_id=391

洛谷该题链接：https://www.luogu.com.cn/problem/P1080

二、题目分析

2.1解题思路

关于此题，网上已有很多文章进行解题分析，解题的关键在于发现相邻的两个大臣以左右手金币数乘积递增排序时，两者获得金币数的最大值最小这一规律，然后借助贪心算法进行求解。
但这一规律并不明显，如何发现这一规律的思考过程大部分文章并未说明，而且关于贪心算法的使用似乎也存在一些逻辑上的不明确。

本文分析如下：

1. 可以分析得出当前大臣所得金币数的另一计算规则，即等于自己及前面所有人的左手乘积除以自己的左右手乘积；
2. 要使第n位大臣所得金币数最小，只可能是第n位大臣的左右手乘积最大的情况下（因为无论如何排列，第n位~第0位的左手乘积都相同）；
3. 由此猜想是否对n位大臣以左右手金币数乘积递增排序时，得金币数最大的大臣金币数最小；
4. 此时采用贪心算法中的反证法，假设某种排序下得金币数最大的大臣金币数最小，设得金币数最大的大臣为第i位大臣，而第i位大臣不是前i位大臣中左右手乘积最大的，那么交换顺序之后，第i位大臣所得金币数减小，与假设相悖，所以确定必须以左右手金币数乘积递增排序才能得到正确结果。

2.2贪心算法

贪心算法，即通过一系列局部最优操作而获得全局最优，但贪心算法需要谨慎使用，一般来说有两种证明方法。

第一种通过反证法，证明如果不按照贪心算法的局部最优操作，那么所得结果就不是最优解，例如部分背包问题就可以使用这种方法证明贪心算法的正确性。

第二种是数学归纳法，也称为证明问题具有最优子结构性质，例如最短路径Dijkstra算法就利用了最优子结构性质。

三、求解代码

3.1解题步骤

根据前文进行的解题分析，解题步骤如下：

1. 首先按照左右手金币数乘积递增的排序规则对n个大臣进行排序；
2. 从第一位大臣开始，依次计算每位大臣的金币数，这一过程需要使用高精度乘除法；
3. 得到每位大臣的金币数，与此前最大金币数进行比较，更新最大金币数。

3.2完整代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+10;
vector<pair<int, int>> vt;
int n;
int ans[N], mul[N], b[N], c[N], d[N], cnt1, cnt2, cnt3, cnt4, cnt;

bool comp(pair<int, int>a, pair<int, int>b)
{
	return a.first*a.second<b.first*b.second;
}

bool greater_eq(int a[], int b[], int last_dg, int len)
{
	if(a[last_dg+len]!=0) return true;
	for(int i=len-1; i>=0; i--)
	{
		if(a[last_dg+i]<b[i+1]) return false;
		if(a[last_dg+i]>b[i+1]) return true;
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n;
	int a1,b1,a0,b0;
	cin>>a0>>b0;
	for(int i=1; i<=n; i++) cin>>a1>>b1, vt.push_back({a1, b1});
	sort(vt.begin(), vt.end(), comp);
	int tmp=a0;
	while(tmp) mul[++cnt1]=tmp%10, tmp/=10;
	for(auto it:vt)
	{
		memset(b, 0, sizeof(b));
		memset(c, 0, sizeof(c));
		memset(d, 0, sizeof(d));
		cnt2=0;
		cnt3=0;
		tmp=it.second;
		while(tmp) b[++cnt2]=tmp%10, tmp/=10;
		for(int i=1; i<=cnt1; i++) d[i]=mul[i];
		cnt4=cnt1;
		for(int i=cnt4-cnt2+1; i>=1; i--)
		{
			while(greater_eq(d, b, i, cnt2))
			{
				for(int j=0; j<cnt2; j++)
				{
					d[i+j]-=b[j+1];
					if(d[i+j]<0) d[i+j]+=10, d[i+j+1]-=1;
				}
				c[i]++;
				if(cnt3==0) cnt3=i;
			}
		}
		if(cnt3>=cnt)
		{
			int code=0;
			if(cnt3==cnt)
			{
				for(int i=cnt; i>=1; i--)
				{
					if(ans[i]>c[i])
					{
						code=1;
						break;
					}
					if(ans[i]<c[i])
					{
						code=0;
						break;
					}
				}
			}
			if(code==0)
			{
				cnt=cnt3;
				for(int i=cnt; i>=1; i--) ans[i]=c[i];
			}
		}
		tmp=it.first;
		for(int i=1; i<=cnt1; i++)
		{
			mul[i]*=tmp;
		}
		for(int i=1; i<=cnt1; i++)
		{
			if(mul[i]>=10) mul[i+1]+=mul[i]/10, mul[i]%=10;
		}
		if(mul[cnt1+1]>0) cnt1++;
		while(mul[cnt1]>=10) mul[cnt1+1]+=mul[cnt1]/10, mul[cnt1]%=10, cnt1++;
	}
	if(cnt==0) cout<<0;
	for(int i=cnt; i>=1; i--) cout<<ans[i];
	cout<<'\n';
	return 0;
}

代码中ans数组存储最大金币数，mul数组存储前面所有大臣左手金币数乘积，b数组存储当前大臣右手金币数，c数组存储当前大臣得到的金币数，d数组作为mul数组的临时副本。
cnt，cnt1， cnt2， cnt3， cnt4分别为各数组存储的高精度数值的位数。

3.3代码提交

蓝桥杯提交结果：

洛谷提交结果：

洛谷有10个测试用例，相较于蓝桥杯5个测试用例严格了许多，初次代码在蓝桥杯解题平台获得满分后，提交到洛谷得到了90分，仔细检查后发现初次代码存在一处错误，且没有考虑最大金币数为0的情况，后续改正后才获得洛谷满分。3.2节的代码为修改后代码。