NOIP 2012 提高组 复赛 第一天 第二题 国王游戏 game 数学推导 AC代码(高精度 低精度 乘 除 比较)+60代码(long long)+20分代码(全排列+深搜dfs)

NOIP 2012 提高组 复赛 第一天 第二题 国王游戏 game  数学推导 AC代码(高精度  低精度 乘 除 比较)+60代码(long long)+20分代码(全排列+深搜dfs)

总目录详见：NOIP 提高组 复赛 试题 目录 信奥 历年

在线测评地址：https://www.luogu.com.cn/problem/P1080

数学推导如下：

我们对于国王身后的两个点来分析

队列可能是这样的：

*	Left	Right
king:	a0​	b0​
p1	a1​	b1​
p2	a2​	b2​

那么我们计算可得ans1​=max(a0/b1,a0*a1/b2​​)

队列也有可能是这样的

*	Left	Right
king:	a0​	b0​
p2	a2​	b2​
p1	a1​	b1​

那么我们计算可得ans2​=max(a0/b2,a0*a2/b1​​)

考虑ans1最优，那么ans1<ans2,

请注意:

(ans1中的)a0/b1<(ans2中的)a0*a2/b1

(ans1中的)a0*a1/b2>(ans2中的)a0/b2

要保证ans1<ans2一定成立,必须(ans1中的)a0*a1/b2<(ans2中的)a0*a2/b1

即a1/b2<a2/b1

即a1*b1<a2*b2

即，按a*b自小到大排序，可以保证是符合题意的最优解。

从成功率来说，还是比较推崇60分代码。

提供一组测试数据

输入：
5
9999 1
9999   1
9999 2
9999 3
9999 4
9999 5
输出：
19990001999800009999

1.AC代码(高精度  低精度 乘 除 比较)

#include <bits/stdc++.h>
#define maxn 1010
#define BASE 10000
using namespace std;
int n,aa[maxn],an,bb[maxn],bn,cc[maxn],cn;
struct node{
	int a,b,c;
}q[maxn];
int cmp(node a,node b){
	return a.c<b.c;
}
void mul(int x){//高精度*低精度 
	int i;
	for(i=1;i<=an;i++)
		aa[i]=aa[i]*x;
	for(i=1;i<=an;i++){
		aa[i+1]+=aa[i]/BASE;
		aa[i]%=BASE;
	}
	//if(aa[an+1])an++;写此句也能过，但总觉不妥 
	while(aa[an+1])an++,aa[an+1]+=aa[an]/BASE,aa[an]%=BASE;	
}
void div(int x){//高精度/低精度 
	int i,yu;
	yu=0;
	for(i=an;i>=1;i--){
		bb[i]=(aa[i]+yu*BASE)/x;
		yu=(aa[i]+yu*BASE)%x;
	}
	bn=an;
	while(!bb[bn])bn--;//去除前导0 
}
int compare(){
	if(bn>cn)return 1;//bb>cc
	if(bn<cn)return -1;//bb<cc
	for(int i=bn;i>=1;i--)//bb==cc
		if(bb[i]>cc[i])return 1;//bb>cc
		else if(bb[i]<cc[i])return -1;//bb<cc
	return 0;//bb==cc
}
int main(){
	int i,j;
	scanf("%d",&n);
	for(i=0;i<=n;i++)scanf("%d%d",&q[i].a,&q[i].b),q[i].c=q[i].a*q[i].b;
	sort(q+1,q+1+n,cmp);
	aa[1]=1,an=1;
	cc[1]=q[0].a/q[1].b,cn=1;
	for(i=1;i<=n;i++){
		mul(q[i-1].a);
		div(q[i].b);
		if(compare()==1){
			cn=bn;
			for(j=bn;j>=1;j--)cc[j]=bb[j];
		}
	}
	printf("%d",cc[cn]); 
	for(i=cn-1;i>=1;i--)printf("%04d",cc[i]);
	return 0;
}

2.60代码(long long)

#include <bits/stdc++.h>
#define LL long long
#define maxn 1100
using namespace std;
struct node{
	LL a,b,c;
}q[maxn];
int cmp(node a,node b){
	return a.c<b.c;
}
LL mx,a=1;
int main(){
	int n,i;
	scanf("%d",&n);
	for(i=0;i<=n;i++){
		scanf("%d%d",&q[i].a,&q[i].b);
		q[i].c=q[i].a*q[i].b; 
	}
	sort(q+1,q+1+n,cmp);
	for(i=1;i<=n;i++)
		a*=q[i-1].a,mx=max(mx,a/q[i].b);
	printf("%lld\n",mx);
	return 0;
}

 3.20分代码(全排列+深搜dfs)

 20分代码(全排列+深搜dfs)如下：

#include <bits/stdc++.h>
using namespace std;
int a[15],b[15],c[15],vis[15],n,mn=2000000000;
void dfs(int step){
	int i;
	if(step==n+1){
		int j,aa=1,mx=0;
		for(j=1;j<=n;j++){
			aa=aa*a[c[j-1]];
			mx=max(mx,aa/b[c[j]]);
		}
		mn=min(mx,mn);
		return;
	}
	for(i=1;i<=n;i++)
		if(!vis[i]){
			vis[i]=1;
			c[step]=i;
			dfs(step+1);
			vis[i]=0;
		}
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<=n;i++)scanf("%d%d",&a[i],&b[i]); 
	dfs(1);
	printf("%d\n",mn);
	return 0;
}