洛谷P1080 国王游戏

题目链接

思路

策略： \large \textbf{策略：} 策略：

记第 i i i 个大臣左手上的数为 A i \rm A_i Ai​ ，右手上的数为 B i \rm B_i Bi​ ，

我们按 A i × B i \rm A_i\times B_i Ai​×Bi​ 对大臣升序排序，所得序列即为最优解。

证明： \large \textbf{证明：} 证明：

假设目前的方案不是按上述方式进行排序的，则一定存在整数 i i i ，使 A i × B i > A i + 1 × B i + 1 \rm A_i \times B_i>A_{i+1}\times B_{i+1} Ai​×Bi​>Ai+1​×Bi+1​ 。

现在试着交换两人的位置，考虑他们交换前后的奖励：

第 i i i 个人	第 i + 1 i+1 i+1 个人
交换前	∏ j = 1 i − 1 A j B i \rm\dfrac{\prod_{j=1}^{i-1}A_j}{B_i} Bi​∏j=1i−1​Aj​​	∏ j = 1 i A j B i + 1 \rm\dfrac{\prod_{j=1}^iA_j}{B_{i+1}} Bi+1​∏j=1i​Aj​​
交换后	∏ j = 1 i − 1 A j B i + 1 \rm\dfrac{\prod_{j=1}^{i-1}A_j}{B_{i+1}} Bi+1​∏j=1i−1​Aj​​	A i + 1 × ∏ j = 1 i − 1 A j B i \rm\dfrac{A_{i+1}\times\prod_{j=1}^{i-1}A_j}{B_i} Bi​Ai+1​×∏j=1i−1​Aj​​

为了方便比较，把四个式子中的 ∏ j = 1 i − 1 A j \rm\prod_{j=1}^{i-1}A_j ∏j=1i−1​Aj​ 全部约去，再同时乘以 B i × B i + 1 \rm B_i\times B_{i+1} Bi​×Bi+1​ ，得到：

第 i i i 个人	第 i + 1 i+1 i+1 个人
交换前	B i + 1 \rm B_{i+1} Bi+1​	A i × B i \rm A_i\times B_i Ai​×Bi​
交换后	B i \rm B_i Bi​	A i + 1 × B i + 1 \rm A_{i+1}\times B_{i+1} Ai+1​×Bi+1​

发现 m a x ( B i , A i + 1 × B i + 1 ) ≤ m a x ( B i + 1 , A i × B i ) \rm max(B_i,A_{i+1}\times B_{i+1})\le max(B_{i+1},A_i\times B_i) max(Bi​,Ai+1​×Bi+1​)≤max(Bi+1​,Ai​×Bi​) ，所以交换后两数最大值不会增加。

根据乘法结合律可以发现这两个人的交换不影响其他人的奖金，所以我们的贪心策略正确。

代码

答案最大可以达到 1000 0 1000 = 1 0 4000 10000^{1000}=10^{4000} 100001000=104000 这个级别的数字，所以要写高精度。

#include<cstdio>
#include<algorithm>
typedef long long ll;

const int P=1e5; //高精压5位
struct node { int x,y; }a[1010];
struct bignum { int len; int c[810]; }prod,ans,t;

inline int cmp(node p,node q) { return (p.x*p.y<q.x*q.y); }
int operator < (bignum a,bignum b) {
	if (a.len!=b.len) return (a.len<b.len);
	for (int i=a.len; i>=0; --i)
		if (a.c[i]!=b.c[i]) return (a.c[i]<b.c[i]);
	return 0;
}
void operator *= (bignum &a,int b) { //高精乘单精
	int x=0; ll t;
	for (int i=0; i<=a.len; ++i) {
		ll t=a.c[i]*b+x; //注意乘法可能爆int
		x=t/P; a.c[i]=t%P;
	}
	if (x) a.c[++a.len]=x;
}
bignum operator / (bignum a,int b) { //高精除以单精
	for (int i=a.len; i; --i) {
		a.c[i-1]+=a.c[i]%b*P; //该语句对压位的位数有所限制
		a.c[i]/=b;
	}
	while (!a.c[a.len]) --a.len;
	a.c[0]/=b;
	return a;
}
void print(bignum a) {
	printf("%d",a.c[a.len]); //无需输出前导零 
	for (int i=a.len-1; i>=0; --i)
		for (int j=1e4; j; j/=10) //直接printf可能会丢失应有的0，故逐位输出
			putchar(a.c[i]/j^48),a.c[i]%=j;
}

int main() {
	int n; scanf("%d",&n);
	for (int i=0; i<=n; ++i)
		scanf("%d%d",&a[i].x,&a[i].y);
	std::sort(a+1,a+n+1,cmp); //排序 
	prod.c[0]=1;
	for (int i=1; i<=n; ++i) {
		prod*=a[i-1].x; t=prod/a[i].y; //注意不要乘自己左手上的数
		if (ans<t) ans=t;
	}
	print(ans);
	return 0;
}