Luogu1080国王游戏|题解

恰逢 $H$ 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

又是一道主程序十分钟高精度一小时的题..

题意转化为

每位大臣获得的金币数分别是：该大臣及前面的所有人的左手上的数的乘积除以他自己左右手上的数之和

显然满足贪心:被除数确定时,需要让除数尽量大

依左右手上数之和排序即可

完整代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define llint long long
using namespace std;
struct bigint {
        llint str[3000],len_;
        bigint operator = (llint al){
                len_ = 0;
                memset(str,0,sizeof(str));
                while (al){
                        str[len_++] = al % 10000;
                        al /= 10000;
                }
                return *this;
        }
        bigint operator *= (llint al){
                str[0] *= al;
                for (int i = 1;i <= len_ ;i ++ ){
                        str[i] = (str[i] * al) + str[i - 1] / 10000;
                        str[i - 1] %= 10000;
                }
                len_ += (str[len_] > 0);
                return *this;
        }
        bigint operator / (llint al){
                bigint ans;
                llint handle = 0;
                for (int i = len_ - 1;i >= 0;-- i){
                        handle = handle * 10000 + str[i];
                        ans.str[i] = handle / al;
                        handle %= al;
                }
                ans.len_ = len_;
                while(!ans.str[ans.len_ - 1])
                        ans.len_ --;
                return ans;
        }
        bool operator < (const bigint &al)const{
                if (len_ != al.len_) return len_ < al.len_;
                for (int i = len_ - 1;i >= 0;--i)
                        if (str[i] != al.str[i]) return str[i] < al.str[i];
                return 0;
        }
        void print(){
                if (!len_) {
                        printf("0\n");
                        return ;
                }
                printf("%lld",str[len_ - 1]);
                for (int i = len_ - 2;i >= 0;--i){
                        if (str[i] < 1000) putchar('0');
                        if (str[i] < 100) putchar('0');
                        if (str[i] < 10) putchar('0');
                        printf("%lld",str[i]);
                }
                printf("\n");
        }
};

struct  xxx{
        llint a,b;
        bool operator < (const xxx &be)const{
                if (a * b != be.a * be.b)
                        return a * b < be.a * be.b;
                return a < be.a;
        }
}arr[20000];

int main (){
        llint n;
        cin >> n;
        for (int i = 0;i <= n;++ i)
                scanf("%lld%lld",&arr[i].a,&arr[i].b);
        bigint mul,ans;
        mul = arr[0].a,ans = (llint)0;
        sort(arr + 1,arr + 1 + n);
        for (int i = 1;i <= n;++ i)
                mul *= arr[i].a,
                ans = max(ans,mul / (arr[i].a * arr[i].b));
        ans.print();
        return 0;
}

以上.