题解：P1080 [NOIP2012 提高组] 国王游戏

· · 题解

思路

  1. 可以用结构体，里面定义连个数 l 和 r，分别表示每个大臣左右手上的数字。

  2. 随后可以弄一个自定义排序，需要让拿到最多金币的人最少，使用到了一个贪心的思想。

  3. 然后写一个两数的比较函数，要用高精度的方法：

    • 如果两个比较的数的长度不相等，就返回谁更大，如果他们的长度差大于 0，a 更大，可如果小于 0，就说明 b 更大。

    • 否则，就比较每一位的数字，来比大小。

  4. 接着是高精度乘，需要考虑进位。

  5. 还有高精度除，需要考虑余数，而被除数的更新则是余数向右移动一位，再加上当前位。

  6. 先算出国王的左手值，在计算当前人获得的金币，然后要更新最大值。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct stu{
    int l;
    int r;
}f[1005];
bool cmp(stu a,stu b){
    return a.l*a.r<b.l*b.r;
}
int n;
vector<int> ans(1,0);
vector<int> t(1,1);
inline vector<int> mul(vector<int> &a,int b){
    vector<int> res;
    int t = 0;
    int len = a.size();
    for(int i=0;i<len;i++){
        t+=a[i]*b;
        res.push_back(t%10);
        t/=10;
    }
    while(t){
        res.push_back(t%10);
        t/=10;
    }
    return res;
}
inline vector<int> div(vector<int> &a,int b){
    vector<int> res;
    int r = 0;
    int len = a.size();
    for(int i=len-1;i>=0;i--){
        r = 10*r+a[i];
        if(r>=b){
            res.push_back(r/b);
            r%=b;
        }else{
            res.push_back(0);
        }
    }
    vector<int> cnt;
    len = res.size();
    for(int i=len-1;i>=0;i--){
        cnt.push_back(res[i]);
    }
    while((cnt.back()==0)&&(cnt.size()>1)){
        cnt.pop_back();
    }
    return cnt;
}
inline int compare(vector<int> &a,vector<int> &b){
    int lenA = a.size();
    int lenB = b.size();
    if(lenA!=lenB){
        int t = lenA-lenB;
        return t;
    }else{
        for(int i=lenA-1;i>=0;i--){
            if(a[i]!=b[i]){
                int t = a[i]-b[i];
                return t;
            }
        }
        return 0;
    } 
}
int main(){
    cin>>n;
    cin>>f[0].l>>f[0].r;
    for(int i=1;i<=n;i++){
        cin>>f[i].l>>f[i].r;
    }
    sort(f+1,f+1+n,cmp);
    t = mul(t,f[0].l);
    for(int i=1;i<=n;i++){
        vector<int> res = div(t,f[i].r);
        if(compare(ans,res)<0){
            ans = res;
        }
        t = mul(t,f[i].l);
    }
    int len = ans.size();
    for(int i=len-1;i>=0;i--){
        cout<<ans[i];
    }
    cout<<endl;
    return 0;
}