国王游戏（算法竞赛进阶指南 P40，贪心 + 大数乘除）

一.题目链接：

国王游戏

二.题目大意：

国王和大臣排队，国王始终排在最前面.

每个人的左右手里各有一个数 a，b.

每 i 位大臣获得钱数为  

现在对大臣重新排队，求最小化最大大臣金额.

三.分析：

按照大臣的 a * b 排序，得到的最大大臣金额是最小的.

证明：

这里选用临项交换的方法.

设第 i 位大臣的 a 为 a[i], b 为 b[i]

第 i + 1 位大臣的 a 为 a[i + 1], b 为 b[i + 1]

则，交换前两位大臣的金额分别为  和 

交换后的金额分别为  和 

提出公因项   

得： 和 

 和 

现在来比较交换前后最大的金额

即： 与 

两遍同乘以  

转化为： 与  

若 

又因为 

所以 

反之若 

又因为 

所以 

综上所得：当  时，交换后更优，反之交换前更优.

因此，将大臣按照  排序后，此时即可取得最小的金额.

证毕.

之后遍历一遍，取最大值即可.

ps：这里要手写大数乘除法（顺便留个模板）.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)5e3;
const ll mod = 998244353;
const int inf = 0x3f3f3f3f;

struct node
{
    int a, b;
}s[M + 5];

bool cmp(node x, node y)
{
    return x.a * x.b < y.a * y.b;
}

int product_len, quot_len, ans_len;
int product[M + 5], quot[M + 5], ans[M + 5];

void mul(int x)
{
    for(int i = 1; i <= product_len; ++i)
        product[i] *= x;
    product_len += 4;
    for(int i = 1; i <= product_len; ++i)
    {
        product[i + 1] += product[i] / 10;
        product[i] %= 10;
    }
    while(!product[product_len])
        product_len--;
}

void div(int x)
{
    int rem = 0;
    bool flag = 1;
    for(int i = product_len; i; --i)
    {
        rem = rem * 10 + product[i];
        quot[i] = rem / x;
        rem %= x;
        if(quot[i] && flag)
        {
            flag = 0;
            quot_len = i;
        }
    }
}

bool bigger()
{
    if(quot_len != ans_len)
        return quot_len > ans_len;
    for(int i = ans_len; i; --i)
    {
        if(quot[i] != ans[i])
            return quot[i] > ans[i];
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i <= n; ++i)
        scanf("%d %d", &s[i].a, &s[i].b);
    sort(s + 1, s + n + 1, cmp);
    product[++product_len] = 1;
    mul(s[0].a);
    for(int i = 1; i <= n; ++i)
    {
        div(s[i].b);
        if(bigger())
        {
            ans_len = quot_len;
            memcpy(ans, quot, sizeof(quot));
        }
        mul(s[i].a);
    }
    for(int i = ans_len; i; --i)
        printf("%d", ans[i]);
    printf("\n");
    return 0;
}