AcWing 114. 国王游戏
原题链接
中等
作者:
啥也不会hh
,
2022-06-27 09:22:47
,
所有人可见
,
阅读 175
//详细题解:https://blog.csdn.net/qq_61935738?spm=1010.2135.3001.5421
/*
解题思路:
根据上述公式推导只要按左右手乘积排序即可;
介绍一个函数:vector<int>(a.rbegin(), a.rend())返回一个新的vector其值为a的逆序
*/
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int n;
PII ps[N];
vector<int> mul(vector<int> a, int b)//高精度乘法
{
int t = 0;
vector<int> c;
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_vec(vector<int> a, int b)//高精度除法
{
int t = 0;
vector<int> c;
bool is_first = false;//防止前导0
for (int i = a.size() - 1; i >= 0; i -- )
{
t = t * 10 + a[i];
int x = t / b;
if (is_first || x)
{
is_first = true;
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 (b.size() > a.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 left, right, mul;
scanf("%d %d", &left, &right);
mul = left * right;
ps[i] = {mul, left};
}
sort(ps + 1, ps + n + 1);
vector<int> res;
vector<int> mul_sum;
res.push_back(0);
mul_sum.push_back(1);
for (int i = 0; i <= n; i ++ )
{
if (i) res = max_vec(res, div_vec(mul_sum, ps[i].first / ps[i].second));
mul_sum = mul(mul_sum, ps[i].second);//计算前i个数的乘积
}
for (int i = res.size() - 1; i >= 0; i -- )
printf("%d", res[i]);
return 0;
}