算法知识点: 贪心
复杂度:
解题思路:
我们先给出做法,再证明其正确性。
做法:直接将所有大臣按左右手上的数的乘积从小到大排序,得到的序列就是最优排队方案。
证明:
我们记第 个大臣左手上的数是 ,右手上的数是 。
假设当前的排队方案不是按 从小到大排序的,则一定存在某两个相邻的人,满足 。
我们现在将这两个人的位置互换,然后考虑他们在交换前和交换后所获得的奖励是多少:
- 交换前:第 个人是 ,第 个人是 ;
- 交换后:第 个人是 ,第 个人是 ;
对比可知 所以交换后两个数的最大值不小于交换前两个数的最大值。
而且交换相邻两个数不会对其他人的奖金产生影响,所以如果存在逆序,则将其交换,得到的结果一定不会比原来更差。
所以从小到大排好序的序列就是最优解,证毕。
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; }