國王的游戲 （貪心 高精度乘 高精度除）

• 國王的游戲

https://ac.nowcoder.com/acm/problem/16561

恰逢 H 國國慶，國王邀請 n 位大臣來玩一個有獎游戲，首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數，然后，讓這 n 位大臣排成一排，國王站在隊伍的最前面，排好隊后，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然后向下取整得到的結果，
國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞盡可能的少，注意，國王的位置始終在隊伍的最前面，

輸入描述:

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

輸出描述:

一個整數，表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數，

輸入

3 
1 1 
2 3 
7 4 
4 6

輸出

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%的資料，保證答案不超過 109 ；對于 100%的資料，有 1 ≤ n ≤1,000,0 ＜ a,b ＜ 10000 ，

題解

我們從普遍的規律入手，在這個隊伍中連續的兩個人A，B，如果他們兩個人調換位置，顯然，受到影響的只有這兩個人，對他們前面和后面的人都沒有影響，

現在我們假設a，b是左手的整數和右手的整數

假設前面i 個人積的值為s，現在如果A在前面 max(s / b_i , (s * a_i )/ b_i+1 )那么,如果調換位置，也就是B換在前面

max(s / b_i+1 , (s * a_i+1 )/ b_i ) 那么 **(s * a_i+1 )/ b_i 大于等于s / b_i **，而 **(s * a_i )/ b_i+1 也顯然大于等于s / b_i+1 **

所以我們要i在前面，就要讓**(s * a_i )/ b_i+1 > (s * a_i+1 )/ b_i **

化簡就可以得到 （a_i * b_i > a_i+1 * b_i+1 )

這個就是貪心的結果

然后還要注意的是資料范圍，要用到高精度

高精度乘法實作原理：

1.由于數字較大，無法使用簡單的資料結構進行存盤，選用陣列和字串來存盤數字，字串方便我們對于高位整數的輸入，而整形陣列的簡便有利于每個位數的計算，結合兩者優點便可實作高精度乘法，

2.實作程序：

(1).通過兩個字串輸入兩個整數

(2).引入兩個陣列，將每個整數切割存盤到陣列里面

(3).進行每一位的運算

(4).處理進位

高精度除法實作原理：高精度除法這一塊比較復雜，它可以分為兩種情況：

第一種情況：高精除以低精，實際上就是對被除的每一位，包括前面的余數都除以除數，

第二種情況：高精除以高精，我就不說了，，，

代碼

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
    int fir,sec;
    bool operator < (const node &a)const{
        return fir*sec<a.fir*a.sec;
    }
}st[1005];
int sum[5050];
int vis[5050];
int arr[5050];
int len=1,tex=1;
void cheng(int b)
{
    for(int i=1;i<=len;i++)
    {
        vis[i]*=b;
    }
    for(int i=1;i<=len;i++)
    {
        vis[i+1]+=vis[i]/10;
        vis[i]%=10;
    }
    if(vis[len+1]!=0) len++;
    while(vis[len]>10)
    {
        vis[len+1]+=vis[len]/10;
        vis[len]%=10;
        len++;
    }
}
void chu(int b)
{
    int t=0,flag=0,ans=0;
    for(int i=len;i>=1;i--)
    {
        t=t*10+vis[i];
        if(t<b&&flag==0) continue;
        else{
            flag=1;
            arr[++ans]=t/b;
            t%=b;
        }
    }/比較金幣數，得到最大金幣數，
    if(ans>tex)
    {
        for(int i=1;i<=ans;i++) sum[i]=arr[i];
        tex=ans;
    }
    else{
        if(ans==tex)
        {
            for(int i=1;i<=ans;i++)
            {
                if(arr[i]>sum[i])
                {
                    for(int i=1;i<=ans;i++)
                    {
                        sum[i]=arr[i];
                    }
                    break;
                }
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<=n;i++)
    {
        cin>>st[i].fir>>st[i].sec;
    }
    sort(st+1,st+1+n);
    sum[1]=vis[1]=1;
    for(int i=1;i<=n;i++)
    {
        cheng(st[i-1].fir);
        chu(st[i].sec);
    }
    for(int i=1;i<=tex;i++) cout<<sum[i];
    cout<<"\n";
    return 0;
}