国王游戏

国王游戏

luogu的忠实支持者

比较有名的贪心题，培训时经常遇到，只是由于涉及到了高精除，一直懒得写。今日将他整理出来

首先是贪心策略

设a，b两个人进行贪心的排序（解决了两个人的排序方式，就解决了全部人的排序方式，只需要重载运算符或写成函数传进stl中就行了）
设a，b前面的人都是最优的且一样，左手乘积为d
plan 1：
a在b前面
最大值=max（d/a的右手，d*a的左手/b的右手）
plan 2：
b在a前面
最大值=max（d/b的右手，d*b的左手/a的右手）


可以明显地看出d/a的右手始终小于d*b的左手/a的右手
同理也b是一样

所以答案就是在d*b的左手/a的右手，d*a的左手/b的右手中选出

两边共同约去d
这样贪心规则就出来了

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	int x;
	int y;
}m[1001];
bool compare(const node &h1,const node &h2)
{
	return h1.x*h1.y<h2.x*h2.y;
}//自定义比较函数
int cheng[500000],tail;//储存乘积，tail为长度，未压位
int ans[500000],taila;//储存答案
int pass[500000],tailp;//储存商
void div(int x)
{
	int i=tail;
	int now=0;
	while(i>0)//高精除低精除法
	{
		now=now*10+cheng[i];
		pass[i]=now/m[x].y;
		now=now%m[x].y;
		i--;
	}
	tailp=tail;
	while(pass[tailp]==0&&tailp)	//更改长度
			tailp--;
}
void max()
{
	bool exchange=false;//是否交换的flag
	if(taila<tailp)
		exchange=true;
	if(taila==tailp)//相同长度比较
		for(int i=tailp;i>=1;i--)
		{
			if(pass[i]>ans[i])
			{
				exchange=true;
				break;
			}
			if(pass[i]<ans[i])
				break;
		}
	if(exchange)	
	{
		for(int i=tailp;i>=1;i--)
			ans[i]=pass[i];
		taila=tailp;
	}
	return ;
}
void mul(int x)
{
	int p=0;
	for(int i=1;i<=tail;i++)
	{
		cheng[i]=cheng[i]*m[x].x+p;
		p=cheng[i]/10;
		cheng[i]%=10;
	}
	while(p)//p有可能不是一位数
	{
		cheng[++tail]=p%10;
		p/=10;
	}
}
int main()
{
	//cin.sync_with_stdio(false);
	int n;
	cin>>n;
	int a,b;
	scanf("%d %d",&a,&b);
	for(int i=1;i<=n;i++)
		scanf("%d %d",&m[i].x,&m[i].y);
	sort(m+1,m+1+n,compare);
	while(a)//将国王的左手转换成高精度储存
	{
		cheng[++tail]=a%10;
		a/=10;
	}
	for(int i=1;i<=n;i++)
	{
		div(i);//高精除低精
		max();//比较，因为有可能最后一个不是最大的
		mul(i);//高精度乘法，当然是低精
	}
	for(int i=taila;i>=1;i--)
		printf("%d",ans[i]);//输出
	return 0;
}