題目描述

恰逢 H 國國慶，國王邀請 n 位大臣來玩一個有獎游戲。首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數。然后，讓這 n 位大臣排成一排，國王站在隊伍的最前面。排好隊后，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然后向下取整得到的結果。

國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞盡可能的少。注意，國王的位置始終在隊伍的最前面。

輸入輸出格式

輸入格式：

第一行包含一個整數 n，表示大臣的人數。

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

接下來 n 行，每行包含兩個整數 a 和 b，之間用一個空格隔開，分別表示每個大臣左手和右手上的整數。

輸出格式：

輸出只有一行，包含一個整數，表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數。

輸入輸出樣例

輸入樣例#1：

3?
1 1?
2 3?
7 4?
4 6?

輸出樣例#1：

2

說明

【輸入輸出樣例說明】

按 1、2、3 號大臣這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 2；

按 1、3、2 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 2；

按 2、1、3 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 2；

按 2、3、1 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 9；

按 3、1、2 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 2；

按 3、2、1 這樣排列隊伍，獲得獎賞最多的大臣所獲得金幣數為 9。

因此，獎賞最多的大臣最少獲得 2 個金幣，答案輸出 2。

【數據范圍】

對于 20%的數據，有 1≤ n≤ 10，0 < a、b < 8；

對于 40%的數據，有 1≤ n≤20，0 < a、b < 8；

對于 60%的數據，有 1≤ n≤100；

對于 60%的數據，保證答案不超過 10^9；

對于 100%的數據，有 1 ≤ n ≤1,000，0 < a、b < 10000。

思路：高精度！

源代碼

#include<cstdio> #include<iostream> using namespace std; int n; int len=1;//表示高精度中字符串的長度 int a[100010],b[100010],c[100010],g[1000010];//a表示乘積，b表示左手，c表示右手 void multiplicative(int x) {int i;for(i=1;i<=len;i++)g[i]*=b[x];for(i=1;i<=len;i++){g[i+1]+=(g[i]/10);//進位g[i]%=10;}len++;while(g[len]>9)//>9的位置上進位{g[len+1]+=(g[len]/10);g[len]%=10;len++;}if(g[len]==0)//刪前導0len--; } void division()//高精除 {int i;for(i=len;i>=1;i--){g[i-1]+=((g[i]%c[n])*10);//將前一位%第n位大臣右手給下一位g[i]/=c[n];}while(g[len]==0)//處理首位len--;if(len==0)//防止減完cout<<1<<endl;} void quick_sort(int l,int r) {int i,j,mid;int temp;i=l;j=r;mid=a[(l+r)/2];while(i<=j){while(a[i]<mid) i++;while(a[j]>mid) j--;if(i<=j){temp=a[i],a[i]=a[j],a[j]=temp;temp=b[i],b[i]=b[j],b[j]=temp;temp=c[i],c[i]=a[j],c[j]=temp;i++;j--;}}if(l<j) quick_sort(l,j);if(i<r) quick_sort(i,r); }int main() {int i;cin>>n;cin>>b[0]>>c[0];for(i=1;i<=n;i++){cin>>b[i]>>c[i];//輸入每人左右手的金幣數a[i]=b[i]*c[i];//兩手金幣數相乘}quick_sort(1,n);//從第一位大臣處開始排序g[1]=b[0];//從國王左手開始乘，賦初值for(i=1;i<n;i++) //所有左手的數字相乘multiplicative(i);division();//最后一個得到的最多，所以由n-1個左手乘積/第n個右手乘積for(i=len;i>=1;i--)//倒序輸出cout<<g[i];return 0; }

?

總結

以上是生活随笔為你收集整理的国王游戏（洛谷-P1080）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。