AcWing 114. 国王游戏
原题链接
中等
作者:
wjie
,
2020-08-11 23:26:42
,
所有人可见
,
阅读 640
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e3 + 5;
struct Node{
int l, r;
bool operator < (const Node& a) const {
return l*r < a.l*a.r;
}
}nodes[N];
vector<int> res;
void compare(vector<int> vec)
{
if (vec.size() > res.size())
{
res = vec;
return;
}
for (int i = res.size()-1; i >= 0; --i)
{
if (vec[i] > res[i])
{
res = vec;
return;
}
}
}
void multiply(vector<int>& mul, int x)
{
int r = 0;
for (int i = 0; i < mul.size(); ++i)
{
mul[i] = mul[i] * x + r;
r = mul[i] / 10000;
mul[i] %= 10000;
}
while (r)
{
mul.push_back(r % 10000);
r /= 10000;
}
}
vector<int> divide(vector<int> div, int x)
{
int r = 0;
for (int i = div.size()-1; i >= 0; --i)
{
div[i] += r * 10000;
r = div[i] % x;
div[i] /= x;
}
while (div.size() && !div.back()) div.pop_back();
return div;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i <= n; ++i)
{
scanf("%d %d", &nodes[i].l, &nodes[i].r);
}
sort(nodes+1, nodes+n+1);
vector<int> mul;
while (nodes[0].l)
{
mul.push_back(nodes[0].l % 10000);
nodes[0].l /= 10000;
}
for (int i = 1; i <= n; ++i)
{
compare(divide(mul, nodes[i].r));
multiply(mul, nodes[i].l);
}
printf("%d", res.back());
for (int i = res.size()-2; i >= 0; --i) printf("%04d", res[i]);
return 0;
}