算法知识点: 贪心

复杂度：

解题思路：

我们先给出做法，再证明其正确性。

做法：直接将所有大臣按左右手上的数的乘积从小到大排序，得到的序列就是最优排队方案。

证明：

我们记第 个大臣左手上的数是 ，右手上的数是 。
假设当前的排队方案不是按 从小到大排序的，则一定存在某两个相邻的人，满足 。
我们现在将这两个人的位置互换，然后考虑他们在交换前和交换后所获得的奖励是多少：

  • 交换前：第 个人是 ，第 个人是 ;
  • 交换后：第 个人是 ，第 个人是 ;

对比可知 所以交换后两个数的最大值不小于交换前两个数的最大值。
而且交换相邻两个数不会对其他人的奖金产生影响，所以如果存在逆序，则将其交换，得到的结果一定不会比原来更差。

所以从小到大排好序的序列就是最优解，证毕。

C++ 代码： 

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef pair <int, int> PII;
const int N = 1010;
 
int n;
PII p[N];
 
vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i++)
    {
        t += a[i] *b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}
 
vector<int> div(vector<int> a, int b)
{
    vector<int> c;
    bool is_first = true;
    for (int i = a.size() - 1, t = 0; i >= 0; i--)
    {
        t = t * 10 + a[i];
        int x = t / b;
        if (!is_first || x)
        {
            is_first = false;
            c.push_back(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}
 
vector<int> max_vec(vector<int> a, vector<int> b)
{
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int> (a.rbegin(), a.rend()) > vector<int> (b.rbegin(), b.rend())) return a;
    return b;
}
 
int main()
{
    cin >> n;
    for (int i = 0; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        p[i] = {
            a *b, a
        };
    }
    sort(p + 1, p + n + 1);
 
    vector<int> product(1, 1);
 
    vector<int> res(1, 0);
    for (int i = 0; i <= n; i++)
    {
        if (i) res = max_vec(res, div(product, p[i].first / p[i].second));
        product = mul(product, p[i].second);
    }
 
    for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
    cout << endl;
 
    return 0;
}



另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ