洛谷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;
}