算法竞赛进阶指南-0x07-国王游戏

2022-03-02 题解

通过冒泡排序可以知道，一直交换一个序列相邻的某两项，可以将序列变成任意想要的样子。

在本题中，两个相邻的大臣x和x+1所能获得的奖励分别为

\frac{\prod_{i=1}^{x-1}a[i]}{b[x]} (1)

和

\frac{\prod_{i=1}^{x}a[i]}{b[x+1]}(2)

如果将它们交换，它们所能获得的奖励又分别变为

\frac{\prod_{i=1}^{x-1}a[i] \times a[x+1]}{b[x]}(3)

和

\frac{\prod^{x-1}_{i=1}a[i]}{b[x+1]}(4)

需要比较的就是 $max((1),(2))$ 和 $max((3),(4))$ 的大小。

注意到这四个式子都有一个公因式 $\prod^{x-1}_{i=1}a[i]$ ，提出来，问题转化为比较下列两个式子的大小

max(\frac{1}{b[x]},\frac{a[x]}{b[x+1]})

max(\frac{a[x+1]}{b[x]},\frac{1}{b[x+1]})

同时乘上 $b[x] \times b[x+1]$ 去掉分母，

max(b[x+1],a[x] \times b[x])

max(a[x+1] \times b[x+1],b[x])

若 $a[x] \geq a[x+1]$ 且 $b[x] \geq b[x+1]$ ，上面两式中的四个值最大的是 $a[x] \times b[x]$ ，因此交换之后所能得到的最大值较小；

若 $a[x+1] \geq a[x]$ 且 $b[x+1] \geq b[x]$ ，上面两式中的四个值最大的是 $a[x+1] \times b[x+1]$ ，不交换所能得到的最大值较小；

由于 $a,b \geq 1$ 恒成立，若 $a[x] \geq a[x+1]$ 且 $b[x] \leq b[x+1]$ ，或者是 $a[x] \leq a[x+1]$ 且 $b[x] \geq b[x+1]$ ，上面两式中的四个值最大的都是

max(a[x] \times b[x],a[x+1] \times b[x+1])

如果 $a[x] \times b[x]$ 比 $a[x+1] \times b[x+1]$ 更大，那么交换后所能得到的最大值更小，否则不交换所能得到的最大值更小。

这里的“交换后所能得到的最大值更小”的意思是：若原序列中的第x+1个大臣排在第x个大臣之前，这两个大臣所能取得的奖励的最大值更小。这样可以按照上面分的四种情况确定大臣之间的排列顺序，照这个次序跑一遍排序之后就可以求出最大奖励的最小值了。

这道题数字很大，要用到高精度

#include <bits/stdc++.h> //用bits可能会因【编译内存超限】导致CE。不过稍微有能的OJ应该都不会了
using namespace std;
const int base = 1e9, dig = 9;
typedef long long ll;
struct BigInt //高精度整数类
{
    int sgn = 1; //表示符号
    vector<int> a = {0};

    friend void Swap(BigInt &a, BigInt &b) //交换
    {
        swap(a.sgn, b.sgn);
        swap(a.a, b.a);
    }

    void trim() //去掉前导零
    {
        for (int i = (int)a.size() - 1; !a[i] && i; i--)
            a.pop_back();
    }

    bool zero() const //判断是否为零
    {
        return (a.size() == 1 && !a[0]);
    }

    BigInt abs() const //取绝对值
    {
        BigInt res = *this;
        res.sgn *= res.sgn;
        return res;
    }

    friend int cmp(const BigInt &x, const BigInt &y) //比较两数绝对值大小
    {
        if (x.a.size() > y.a.size())
            return 1;
        else if (x.a.size() < y.a.size())
            return -1;
        for (int i = (int)x.a.size() - 1; i >= 0; i--)
        {
            if (x.a[i] > y.a[i])
                return 1;
            else if (x.a[i] < y.a[i])
                return -1;
        }
        return 0;
    }

    BigInt add(const BigInt &v) //复杂度O(n)
    {
        int len = a.size(), vlen = v.a.size();
        int mlen = max(len, vlen);
        BigInt res;
        a.resize(mlen + 1, 0);
        for (int i = 0; i < mlen; i++)
        {
            if (i < vlen)
                a[i] += v.a[i];
            if (a[i] >= base)
                a[i] -= base, a[i + 1]++;
        }
        this->trim();
        return *this;
    }

    BigInt sub(const BigInt &v) //复杂度O(n)
    {
        int vlen = v.a.size();
        for (int i = 0; i < vlen; i++)
        {
            a[i] -= v.a[i];
            if (a[i] < 0)
                a[i] += base, a[i + 1]--;
        }
        this->trim();
        return *this;
    }

    BigInt mul_simple(const BigInt &v) const //复杂度O(n*n)
    {
        int len = a.size(), vlen = v.a.size();
        BigInt res;
        res.sgn = sgn * v.sgn;
        res.a.resize(len + vlen);
        for (int i = 0; i < len; i++)
        {
            if (a[i])
            {
                for (int j = 0; j < vlen; j++)
                {
                    ll cur = res.a[i + j] + (ll)a[i] * v.a[j];
                    res.a[i + j + 1] += (int)(cur / base);
                    res.a[i + j] = (int)(cur % base);
                }
            }
        }
        res.trim();
        return res;
    }

    friend pair<BigInt, BigInt> divmod(const BigInt &a1, const BigInt &b1) //复杂度O(n*n)
    {
        ll norm = base / (b1.a.back() + 1), s1, s2;
        BigInt a = a1.abs() * norm, b = b1.abs() * norm, q, r;
        int alen = a.a.size(), blen = b.a.size();
        q.a.resize(alen);
        for (int i = alen - 1; i >= 0; i--)
        {
            r = r * base;
            r += a.a[i];
            s1 = s2 = 0;
            if ((int)r.a.size() > blen)
                s1 = r.a[blen];
            if ((int)r.a.size() > blen - 1)
                s2 = r.a[blen - 1];
            ll d = ((ll)base * s1 + s2) / b.a.back();
            r -= b * d;
            while (r.sgn < 0)
                r += b, --d;
            q.a[i] = d;
        }
        q.sgn = a1.sgn * b1.sgn;
        r.sgn = a1.sgn;
        q.trim();
        r.trim();
        auto res = make_pair(q, r / norm);
        if (res.second.sgn < 0)
            res.second += b1;
        return res;
    }

    BigInt operator%(const BigInt &v) const
    {
        return divmod(*this, v).second;
    }

    BigInt operator=(ll v) // long long 赋值
    {
        sgn = 1;
        if (v < 0)
            sgn = -1, v = -v;
        a.clear();
        while (v)
        {
            a.push_back(v % base);
            v /= base;
        }
        return *this;
    }

    BigInt operator=(string s) // string 赋值
    {
        sgn = 1;
        a.clear();
        int k = 0;
        if (s[k] == '-')
            sgn = -sgn, k++;
        for (int i = (int)s.size() - 1; i >= k; i -= dig)
        {
            int x = 0;
            for (int j = max(k, i - dig + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            a.push_back(x);
        }
        return *this;
    }

    void operator+=(const BigInt &v)
    {
        if (sgn == v.sgn)
            add(v);
        else if (cmp(*this, v) >= 0)
            sub(v);
        else
        {
            BigInt t = v;
            Swap(*this, t);
            sub(t);
        }
    }

    void operator+=(const ll &t)
    {
        BigInt v;
        v = t;
        if (sgn == v.sgn)
            add(v);
        else if (cmp(*this, v) >= 0)
            sub(v);
        else
        {
            BigInt t = v;
            Swap(*this, t);
            sub(t);
        }
    }

    void operator-=(const BigInt &v)
    {
        if (sgn == v.sgn)
        {
            if (cmp(*this, v) >= 0)
                sub(v);
            else
            {
                BigInt t = v;
                swap(*this, t);
                sub(t);
                sgn = -sgn;
            }
        }
        else
            add(v);
    }

    BigInt operator*(const BigInt &v) const
    {
        return mul_simple(v);
    }

    BigInt operator*(const ll &v) const
    {
        BigInt t;
        t = v;
        return mul_simple(t);
    }
    BigInt operator/(const BigInt &v) const
    {
        return divmod(*this, v).first;
    }

    BigInt operator/(ll v) const
    {
        BigInt t;
        if (llabs(v) >= base)
        {
            t = v;
            return *this / BigInt(t);
        }
        t = *this;
        if (v < 0)
            t.sgn = -t.sgn, v = -v;
        for (int i = (int)t.a.size() - 1, rem = 0; i >= 0; i--)
        {
            ll cur = t.a[i] + rem * (ll)base;
            t.a[i] = (int)(cur / v);
            rem = (int)(cur % v);
        }
        t.trim();
        return t;
    }

    bool operator<(const BigInt &v) const //直接比较两个数的大小
    {
        if (sgn != v.sgn)
            return sgn < v.sgn;
        if (a.size() != v.a.size())
            return a.size() * sgn < v.a.size() * v.sgn;
        for (int i = (int)a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sgn < v.a[i] * sgn;
        return 0;
    }

    bool operator>(const BigInt &v) const
    {
        return v < *this;
    }

    bool operator<=(const BigInt &v) const
    {
        return !(v < *this);
    }

    bool operator>=(const BigInt &v) const
    {
        return !(*this < v);
    }

    bool operator==(const BigInt &v) const
    {
        return !(*this < v) && !(v < *this);
    }

    bool operator!=(const BigInt &v) const
    {
        return *this < v || v < *this;
    }

    friend ostream &operator<<(ostream &out, const BigInt &v)
    {
        if (v.sgn == -1 && !v.zero())
            out << '-';
        out << v.a.back();
        for (int i = (int)v.a.size() - 2; i >= 0; i--)
            out << setw(dig) << setfill('0') << v.a[i];
        return out;
    }
};
struct node
{
    long long a, b;
    bool operator<(const node &x) const
    {
		//虽然分析过程中都用大于等于判断，但是规定排序方法时需要使用严格的大于和小于号，否则会导致RE
        if (a < x.a && b < x.b)
            return true;
        if (a > x.a && b > x.b)
            return false;
        return a * b < x.a * x.b;
    }
} p[10005];
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, i;
    cin >> n;
    for (i = 0; i <= n; i++)
        cin >> p[i].a >> p[i].b;
    sort(p + 1, p + 1 + n);
    BigInt t, res;
    t = p[0].a;
    res = -1;
    for (i = 1; i <= n; i++)
    {
        if (res < t / p[i].b)
            res = t / p[i].b;
        t = t * p[i].a;
    }
    cout << res;
    return 0;
}