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;
}