Description
恰逢H國(guó)國(guó)慶，國(guó)王邀請(qǐng)n位大臣來(lái)玩一個(gè)有獎(jiǎng)游戲。首先，他讓每個(gè)大臣在左、右

手上面分別寫下一個(gè)整數(shù)，國(guó)王自己也在左、右手上各寫一個(gè)整數(shù)。然后，讓這n位大臣排

成一排，國(guó)王站在隊(duì)伍的最前面。排好隊(duì)后，所有的大臣都會(huì)獲得國(guó)王獎(jiǎng)賞的若干金幣，每

位大臣獲得的金幣數(shù)分別是：排在該大臣前面的所有人的左手上的數(shù)的乘積除以他自己右

手上的數(shù)，然后向下取整得到的結(jié)果。

國(guó)王不希望某一個(gè)大臣獲得特別多的獎(jiǎng)賞，所以他想請(qǐng)你幫他重新安排一下隊(duì)伍的順序，

使得獲得獎(jiǎng)賞最多的大臣，所獲獎(jiǎng)賞盡可能的少。注意，國(guó)王的位置始終在隊(duì)伍的最前面。

Input
輸入文件為game.in。

第一行包含一個(gè)整數(shù)n，表示大臣的人數(shù)。

第二行包含兩個(gè)整數(shù)a和b，之間用一個(gè)空格隔開，分別表示國(guó)王左手和右手上的整數(shù)。

接下來(lái)n行，每行包含兩個(gè)整數(shù)a和b，之間用一個(gè)空格隔開，分別表示每個(gè)大臣左手

和右手上的整數(shù)。

Output
輸出文件名為game.out。

輸出只有一行，包含一個(gè)整數(shù)，表示重新排列后的隊(duì)伍中獲獎(jiǎng)賞最多的大臣所獲得的

金幣數(shù)。

Sample Input
3
1 1
2 3
7 4
4 6

Sample Output
2
【輸入輸出樣例說(shuō)明】
按1、2、3號(hào)大臣這樣排列隊(duì)伍，獲得獎(jiǎng)賞最多的大臣所獲得金幣數(shù)為2；
按1、3、2這樣排列隊(duì)伍，獲得獎(jiǎng)賞最多的大臣所獲得金幣數(shù)為2；
按2、1、3這樣排列隊(duì)伍，獲得獎(jiǎng)賞最多的大臣所獲得金幣數(shù)為2；
按2、3、1這樣排列隊(duì)伍，獲得獎(jiǎng)賞最多的大臣所獲得金幣數(shù)為9；
按3、1、2這樣排列隊(duì)伍，獲得獎(jiǎng)賞最多的大臣所獲得金幣數(shù)為2；
按3、2、1這樣排列隊(duì)伍，獲得獎(jiǎng)賞最多的大臣所獲得金幣數(shù)為9。
因此，獎(jiǎng)賞最多的大臣最少獲得2個(gè)金幣，答案輸出2。

Data Constraint

Hint
對(duì)于20%的數(shù)據(jù)，有1≤ n≤ 10，0 < a、b < 8；
對(duì)于40%的數(shù)據(jù)，有1≤ n≤20，0 < a、b < 8；
對(duì)于60%的數(shù)據(jù)，有1≤ n≤100；
對(duì)于60%的數(shù)據(jù)，保證答案不超過(guò)10^9；
對(duì)于100%的數(shù)據(jù)，有1 ≤ n ≤1,000，0 < a、b < 10000。

.
.
.
.
.
.
分析
設(shè)緊挨著的兩個(gè)人a,b的左右手?jǐn)?shù)字分別為L(zhǎng)a,Lb,Ra,Rb，設(shè)a和b前面的所有人的左手的數(shù)字的乘積為S，可以發(fā)現(xiàn)，交換ab的順序不會(huì)影響ab前面所有人得到的金幣數(shù)，也不會(huì)影響ab后面所有人得到的金幣數(shù)目，那么可以假設(shè)讓a排在b前面比讓b排在a前面的結(jié)果更優(yōu)：

a在b前時(shí)：
a獲得的金幣數(shù)為：S/Ra ———– #1
b獲得的金幣數(shù)為：SLa/Rb ———–#2
b在a前時(shí)：
a獲得的金幣數(shù)為：SLb/Ra ———–#3
b獲得的金幣數(shù)為：S/Rb ————#4

那么要想讓假設(shè)成立，就必須有：max(#1 , #2) < max(#3 , #4)———#5
很明顯可以看出，#1 < #3 ,# < #4
如果要#5成立，還必須有#3 > #2 ，即 SLb/Ra > SLa/Rb
化簡(jiǎn)得到：LbRb > LaRa
所以得到左右手?jǐn)?shù)字乘積小的排在前面會(huì)使得結(jié)果更優(yōu)。

最后，要用高精計(jì)算。

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int a[20000],b[20000],w[20000],d[20000],maxx[100000],len,f,maxxlen,a1[100000],a2[100000]; char str[100000];void kp(int l,int r) {if (l>r) return;int i=l,j=r,mid=w[(l+r)/2];do {while (w[i]<mid) i++;while (w[j]>mid) j--;if (i<=j){a[0]=a[i];a[i]=a[j];a[j]=a[0];b[0]=b[i];b[i]=b[j];b[j]=b[0];w[0]=w[i];w[i]=w[j];w[j]=w[0];i++;j--;}}while (i<=j);kp(l,j);kp(i,r); }void cheng(int a[],int b) {memset(d,0,sizeof(d));for(int i=1;i<=len;i++) d[i]=a[i]*b;for (int i=1;i<=len;i++)if (d[i]/10){d[i+1]+=d[i]/10;d[i]%=10;}while (d[len+1]) len++;while (d[len]/10){d[len+1]+=d[len]/10;d[len]%=10;len++;}for (int i=1;i<=len;i++) a[i]=d[i]; }void chu(int a[],int b) {memset(d,0,sizeof(d)); int x=0;for(int i=1;i<=len;i++){d[i]=(a[i]+x*10)/b;x=(a[i]+x*10)%b;}int pd=0;for (int i=1;i<=len;i++)if (d[i]!=0){pd=1;break;}if (pd!=0){int i=1;while (d[i]==0) i++;f=i;while (i<=len){if (d[i]>maxx[i]&&len-f+1==maxxlen||len-f+1>maxxlen){for (int j=f;j<=len;j++) maxx[j]=d[j];maxxlen=len-f+1;break;}if (maxxlen>len-f+1||d[i]<maxx[i]) break;i++;}} }int main() {int n,aa,bb;scanf("%d",&n);scanf("%d%d",&aa,&bb);for (int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);w[i]=a[i]*b[i];}kp(1,n);int i=0;while (aa!=0){str[i]=aa%10+'0';aa/=10;i++;}len=strlen(str);for (int i=1;i<=len;i++) a1[i]=str[i-1]-'0';for (int i=1;i<=len;i++) a2[i]=str[len-i]-'0';for (int i=1;i<=n;i++){chu(a2,b[i]);cheng(a1,a[i]);for (int j=1;j<=len;j++) a2[j]=a1[len-j+1];}for (int i=f;i<=maxxlen+f-1;i++) cout<<maxx[i];return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10292780.html

總結(jié)

以上是生活随笔為你收集整理的国王游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。