You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
82 lines
2.0 KiB
82 lines
2.0 KiB
#include<bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
const int N = 1010;
|
|
int n;
|
|
struct Person {
|
|
int left, right;
|
|
} person[N];
|
|
|
|
bool cmp(const Person &a, const Person &b) {
|
|
return a.left * a.right < b.left * b.right;
|
|
}
|
|
|
|
//高精度乘法
|
|
vector<int> mul(vector<int> &A, int b) {
|
|
vector<int> C;
|
|
int t = 0;
|
|
for (int i = 0; i < A.size() || t; i++) {
|
|
if (i < A.size()) t += A[i] * b;
|
|
C.push_back(t % 10);
|
|
t /= 10;
|
|
}
|
|
while (C.size() > 1 && C.back() == 0) C.pop_back();
|
|
return C;
|
|
}
|
|
|
|
//高精度除法
|
|
vector<int> div(vector<int> &A, int b, int &r) {
|
|
vector<int> C;
|
|
r = 0;
|
|
for (int i = A.size() - 1; i >= 0; i--) {
|
|
r = r * 10 + A[i];
|
|
C.push_back(r / b);
|
|
r %= b;
|
|
}
|
|
reverse(C.begin(), C.end());
|
|
while (C.size() > 1 && C.back() == 0) C.pop_back();
|
|
return C;
|
|
}
|
|
|
|
//获取两个vector<int>中较大的那个
|
|
vector<int> max_vec(vector<int> a, vector<int> b) {
|
|
if (a.size() > b.size()) return a;
|
|
if (a.size() < b.size()) return b;
|
|
for (int i = a.size() - 1; i >= 0; i--) {
|
|
if (a[i] > b[i]) return a;
|
|
if (a[i] < b[i]) return b;
|
|
}
|
|
return a;
|
|
}
|
|
|
|
int main() {
|
|
//优化输入
|
|
ios::sync_with_stdio(false);
|
|
cin >> n;
|
|
//输入
|
|
for (int i = 0; i <= n; i++)
|
|
cin >> person[i].left >> person[i].right;
|
|
|
|
//排序,国王不参加排序
|
|
sort(person + 1, person + n + 1, cmp);
|
|
|
|
//连乘各放入国王
|
|
vector<int> lcj;
|
|
lcj.push_back(person[0].left);
|
|
|
|
//结果
|
|
vector<int> res;
|
|
res.push_back(0);//在做高精度时，也需要进行一步初始化
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
int r;//余数，本题中因为只需要下取整，所以余数无意义
|
|
res = max_vec(res, div(lcj, person[i].right, r));
|
|
lcj = mul(lcj, person[i].left);
|
|
}
|
|
//倒序输出高精度数组中的值
|
|
for (int i = res.size() - 1; i >= 0; i--)
|
|
printf("%d", res[i]);
|
|
return 0;
|
|
}
|