【YBTOJ】【Luogu P1080】国王游戏

题目大意：

两个数列 (a_i,b_i)。位置 (i) 的价值是 (frac{prod_{j=0}^{i-1}a_j}{b_i})，现在给两个数列 (a,b) 同时排列，问怎么排使得最大权值最小。

正文：

设 (s_i) 表示 (prod_{j=0}^{i}a_j)，考虑贪心邻相交换：

当前位置	(a)	(b)	交换前权值
(i)	(a_i)	(b_i)	(frac{s_{i-1}}{b_i})
(i+1)	(a_{i+1})	(b_{i+1})	(frac{s_{i-1} imes a_i}{b_{i+1}})

( ext{ans}_1=max{frac{s_{i-1}}{b_i},frac{s_{i-1} imes a_i}{b_{i+1}}})

交换后：

当前位置	(a)	(b)	交换后权值
(i+1)	(a_{i+1})	(b_{i+1})	(frac{s_{i-1}}{b_{i+1}})
(i)	(a_i)	(b_i)	(frac{s_{i-1} imes a_{i+1}}{b_i})

( ext{ans}_2=max{frac{s_{i-1}}{b_{i+1}},frac{s_{i-1} imes a_{i+1}}{b_i}})

显然 (frac{s_{i-1}}{b_i}<frac{s_{i-1} imes a_{i+1}}{b_i})。

若 ( ext{ans}_1< ext{ans}_2)，那么 (frac{s_{i-1} imes a_i}{b_{i+1}}<frac{s_{i-1} imes a_{i+1}}{b_i})。

对这个式子变形：

[egin{aligned}frac{s_{i-1} imes a_i}{b_{i+1}}&<frac{s_{i-1} imes a_{i+1}}{b_i}\ s_{i-1} imes a_i imes b_i&<s_{i-1} imes a_{i+1} imes b_{i+1}\ a_i imes b_i&<a_{i+1} imes b_{i+1} end{aligned}]

也就是说，答案尽量小的话，(a_i imes b_i) 必须小，那就按这个为 key 对它们排序。

接下来就更简单了，枚举 (i) 的权值，取个最大就行啦!

由于本题很毒瘤，所以开个高精度。

代码：

const int N = 1010;

struct node
{
	int a[50010];
    int &operator [](int x){return a[x];}
	node()
	{
		memset (a, 0, sizeof a);
	}
	inline void print()
	{
		for (int i = a[0]; i >= 1; i--)
			printf ("%d", a[i]);
	}
}ans, tool;

node operator * (node A, ll a)  
{
	int s = 0, g = 0;
	node C;
	int len = A[0];
	for (int i = 1; i <= len + 10; i++)
	{
		s = A[i] * a + g, g = s / 10;
		C[i] = s % 10;
		if (!s && !g && i > len) break;
		C[0] = i; 
	}
	return C;
}

node operator / (node A, ll a)  
{
	int s = 0;
	node C;
	C[0] = A[0];
	for (int i = A[0]; i; i--)
	{
		s = s * 10 + A[i];
		C[i] = s / a, s %= a;
	}
	while (!C[C[0]] && C[0] > 1) --C[0];
	return C;
}

node Max (node a, node b)
{
	if (a[0] > b[0]) return a;
	if (a[0] < b[0]) return b;
	for (int i = a[0]; i >= 1; i--)
	{
		if (a[i] > b[i]) return a;
		if (a[i] < b[i]) return b;
	}
	return a;
}

struct INp 
{
	ll x, y;
}a[N];

bool cmp (INp a, INp b)
{
	return a.x * a.y < b.x * b.y;
}

int n, m;

int main()
{
	scanf ("%d", &n);
	for (int i = 0; i <= n; i++)
		scanf ("%lld%lld", &a[i].x, &a[i].y);
	sort (a + 1, a + 1 + n, cmp);
	tool[1] = tool[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		tool = tool * a[i - 1].x;
		ans = Max(ans, tool / a[i].y);
	}
	ans.print();
    return 0;
}