P1080. 国王游戏

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 759 阅读时长 ≈ 3 分钟

考点

  • 贪心
  • 高精度

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e4 + 50;

class BigInt
{
public:
    int len_;
    int arr_[10500];
    BigInt(int x = 0)
    {
        memset(arr_, 0, sizeof(arr_));
        for (len_ = 1; x; ++len_)
            arr_[len_] = x % 10, x /= 10;
        --len_;
    }
    int &operator[](int x)
    {
        return arr_[x];
    }
    void print()
    {
        for (int i = max(1, len_); i >= 1; --i)
        {
            cout << arr_[i];
        }
    }
    void flatten(int len)
    {
        len_ = len;
        for (int i = 1; i <= len_; ++i)
        {
            if (arr_[i] >= 10)
            {
                arr_[i + 1] += arr_[i] / 10;
                arr_[i] %= 10;
            }
        }
        while (!arr_[len_])
            --len_;
    }
};

BigInt operator*(BigInt a, int b)
{
    BigInt c;
    int len = a.len_;
    for (int i = 1; i <= len; ++i)
    {
        c[i] += a[i] * b;
    }
    c.flatten(len + 11);
    return c;
}

bool greater_eq(BigInt a, BigInt b, int lst_dg)
{
    if (lst_dg <= 0)
        return false;
    if (a[lst_dg + b.len_] != 0)
        return true;
    for (int i = b.len_; i >= 1; --i)
    {
        if (a[lst_dg + i - 1] > b[i])
            return true;
        if (a[lst_dg + i - 1] < b[i])
            return false;
    }
    return true;
}

BigInt operator/(BigInt a, int b)
{
    BigInt c;
    long long r = 0;
    for (int i = a.len_; i >= 1; --i)
    {
        c[i] += (r * 10 + a[i]) / b;
        r = (r * 10 + a[i]) % b;
    }
    c.flatten(a.len_);
    return c;
}

struct Node
{
    int a_, b_;
} arr[10005];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; ++i)
        cin >> arr[i].a_ >> arr[i].b_;
    sort(arr + 1, arr + 1 + n, [](Node a, Node b) -> bool
         { return (1ll * a.a_ * a.b_) < (1ll * b.a_ * b.b_); });
    BigInt mul(arr[0].a_), ans, div;
    for (int i = 1; i <= n; ++i)
    {
        div = mul / arr[i].b_;
        if (!greater_eq(ans, div, ans.len_ - div.len_ + 1))
            ans = div;
        mul = mul * arr[i].a_;
    }
    ans.print();
    return 0;
}

思路

题眼有获得奖赏最多的大臣，所获奖赏尽可能的少，很容易想到以下几种可能

  • 二分，但是貌似没有可以二分的东西...
  • 状压DP，但是状态存不下啊啊...
  • 贪心

贪心主要分析单调性，所以将视角放在相邻两个元素；假设有相邻位置i < j，i之前的总乘积为S

当前两个位置的大臣各自所获金币的最大值V1，两个大臣的位置交换后，各自所获金币的最大值V2

根据题意，以V1 < V2的优先级进行重新排序 \[ \text{交换之前，}\max \left( \underset{i\text{位置}}{\underbrace{\frac{S}{b_i}}}\,\,_{,}^{\,\,}\underset{j\text{位置}}{\underbrace{\frac{S\times a_i}{b_j}}} \right) =V_1 \\ \text{交换之后，}\max \left( \underset{i\text{位置}}{\underbrace{\frac{S}{b_j}}}\,\,_{,}^{\,\,}\underset{j\text{位置}}{\underbrace{\frac{S\times a_j}{b_i}}} \right) =V_2 \] 两边都可以约去S，变成 \[ \max \left( \frac{1}{b_i}_{,}^{\,\,}\frac{a_i}{b_j} \right) <\max \left( \frac{1}{b_j}_{,}^{\,\,}\frac{a_j}{b_i} \right) \] 两边通分一下，变成 \[ \max \left( b_j\,\,, a_i\times b_i \right) <\max \left( b_i\,\,, a_j\times b_j \right) \] 设ai，bi，aj，bj分别为A、B、C、D，式子可以简化为 \[ \max \left( D\,\,, A\cdot B \right) <\max \left( B\,\,, C\cdot D \right) \] 如果右侧式子B为最大，即B大于C乘D；由于A只能为正整数，那么A乘B也大于D，两侧式子就变成了： \[ A\cdot B<B \] 这可能吗？所以B可以直接去掉，左侧的D也同理直接去掉，就得到了最终的贪心单调性 \[ A\cdot B<C\cdot D \]

\[ a_i\cdot b_i<a_j\cdot b_j\,\,, i<j \]

剩下的部分就不难了，套高精度乘低精度以及高精度除低精度的模板即可

这里不能用高精除高精的模板！！！！会超时！！！！