洛谷P1080 国王游戏

url: https://www.luogu.com.cn/problem/P1080

tag:
NOIP2012 提高组，贪心，高精度

思路：
用贪心的策略，将大臣按照左右手金币数量的乘积从小到大排序，贪心证明: https://www.luogu.com.cn/article/2xwnkq6p . 然后因为数据范围比较大又用到了乘除所以需要使用高精度，同时配合写一个比较函数。

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int n;
typedef pair<int, int> PII;
vector<PII> d;
bool cmp(PII &a, PII &b)
{
    return a.first * a.second < b.first * b.second;
}
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;
    }
    while (!C.back() && C.size() != 1) C.pop_back();
    return C;
}
vector<int> div(vector<int> &A, int b)
{
    vector<int> C;
    reverse(A.begin(), A.end());
    int t = 0;
    for (int i = 0; i < A.size(); i ++)
    {
        t = t * 10 + A[i];
        C.push_back(t / b);
        t %= b;
    }
    reverse(C.begin(), C.end());
    while (!C.back() && C.size() > 1) C.pop_back();
    reverse(A.begin(), A.end());
    return C;
}
bool rescmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();
    else
    {
        for (int i = A.size() - 1; i >= 0; i ++)
        {
            if (A[i] == B[i]) continue;
            else return A[i] > B[i];
        }
    }
}
int main()
{
    cin >> n;
    PII king;
    cin >> king.first >> king.second;
    for (int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        d.push_back({a, b});
    }
    sort(d.begin(), d.end(),cmp);
    d.insert(d.begin(),king);
    vector<int> res(1, 0);
    vector<int> tmp(1, 1);
    for (int i = 1; i < d.size(); i ++)
    {
        tmp = mul(tmp,d[i - 1].first);
        auto tmmp = div(tmp, d[i].second);
        if (rescmp(tmmp, res)) res = tmmp;
    }
    for (int i = res.size() - 1; i >= 0; i --) cout << res[i];
    cout << endl;
    return 0;
}