记录编号	197477	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]国王游戏	最终得分	100
用户昵称	lingyixiaoyao	是否通过	通过
代码语言	C++	运行时间	0.064 s
提交时间	2015-10-23 21:43:55	内存使用	0.38 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
struct node
{
	int x,y,w;
};
 
const int maxn=1000+10;
int n;
node a[maxn];
int x[5000],y[5000],ans[5000];
int lenx,leny,len;
 
bool comp(node i,node j);
void chu(int m);
void cheng(int m);
bool ok();
 
int main()
{
	freopen("kinggame.in","r",stdin);
	freopen("kinggame.out","w",stdout);
	
	cin>>n;
	for (int i=0; i<=n; i++)
	{
		cin>>a[i].x>>a[i].y;
		a[i].w=a[i].x*a[i].y;
	}
	sort(a+1,a+n+1,comp);
	
	//x=a[0].x;
	x[1]=a[0].x; lenx=1;
	for (int i=1; i<=n; i++)
	{
		//y=x/a[i].y;
		chu(a[i].y);
		//if (y>ans) ans=y;
		if (ok())
		{
			len=leny;
			memcpy(ans,y,sizeof(y));
		}
		//x*=a[i].x;
		cheng(a[i].x);
	}
	for (int i=len; i>=1; i--)
		cout<<ans[i];
	cout<<endl;
	return 0;
}
bool comp(node i,node j)
{
	if (i.w<j.w) return true;
	else return false;
}
void chu(int m)
{
	memset(y,0,sizeof(y));
	int d=0;
	int p=lenx;
	leny=lenx;
	while (p>0)
	{
		d=d*10+x[p];
		y[p]=d/m;
		d%=m;
		p--;
	}
	while (leny>0 && y[leny]==0) leny--;
}
void cheng(int m)
{
	for (int i=1; i<=lenx; i++)
	{
		x[i]*=m;
	}
	for (int i=1; i<=lenx; i++)//处理进位 
	{
		x[i+1]+=x[i]/10;
		x[i]%=10;
	}
	while(x[lenx+1]>0)//处理高位 
	{
		lenx++;
		x[lenx+1]+=x[lenx]/10;
		x[lenx]%=10;
	}
}
bool ok()//判断是否更大 
{
	if (leny>len) return true;
	if (leny==len)
	{
		int p=len;
		while (p>0)
		{
			if (y[p]>ans[p]) return true;
			p--;
		}
	}
	return false;
}