50分求助
查看原帖
50分求助
457002
szhl0803楼主2022/8/21 18:46
//P1080 [NOIP2012 提高组] 国王游戏
#include <bits/stdc++.h>
#define maxn 10000

using namespace std;

//mod
struct bigint{
	int a[maxn],len;
	bigint(int x=0)
	{
		memset(a,0,sizeof(a));
		for(len = 1;x;len++)
		{
			a[len] = x%10;x/=10;
		}
	}
	int &operator[](int in)
	{
		return a[in];
	}
	void fellet(int lenx)
	{
		len = lenx;
		for(int i=1;i<=lenx;i++)
		{
			a[i+1]+=a[i]/10;
			a[i] %= 10;
		}
		while(!a[len])len--;
	}
	void print()
	{
		for(int i=max(len,1);i>=1;i--)
		printf("%d",a[i]);
	}
};

bigint operator*(bigint a,int b)
{
	int l = a.len;
	bigint c;
	for(int i=1;i<=l;i++)
	{
		c[i] = a[i] * b;
	}
	c.fellet(l+11);
	return c;
}

bigint operator/(bigint a,int b)
{
	bigint c;
	int l = a.len;
	int m = 0;
	for(int i=l;i>=1;i--)
	{
		m = m * 10 + a[i];
		c[i] = m / b;
		m = m - b * c[i];
	}
	c.fellet(l);
	return c;
}

bigint bigmax(bigint a,bigint b)
{
	int la = a.len;
	int lb = b.len;
	if(la!=lb)return la>lb?a:b;
	string ua,ub;
	for(int i=la;i>=1;i--)
	{
		ua.push_back(a[i]+48);
		ub.push_back(b[i]+48);
	}
	return ua>ub?a:b;
}

struct node{
	int l,r;
}p[100100];

int n;

void input();

bool cmp(node a,node b)
{
	return a.r<b.r;
}

int main()
{
	input();
	bigint sumx(1),ans;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		sumx = sumx * p[i-1].l;
		bigint c;
		c = sumx / p[i].r;
		ans = bigmax(ans,c);
	}
	ans.print();
	return 0;
 } 
 
void input()
{
	scanf("%d",&n);
	for(int i=0;i<=n;i++)scanf("%d%d",&p[i].l,&p[i].r); 
}
2022/8/21 18:46
加载中...