恰逢 H H国国庆,国王邀请 nn 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 nn 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
输入格式
第一行包含一个整数 nn,表示大臣的人数。
第二行包含两个整数 aa和 bb,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 n n行,每行包含两个整数 aa 和 bb,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
输出格式
一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
注意以大臣的左右手之和从小到大排序,证明在这里不多说有兴趣的小伙伴可以手动推一遍,还需要注意的是需要找到大臣中的最大金币数量
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int> mul(vector<int>a, int b)
{
vector<int>c;
int t = 0;
for (int i = a.size() - 1; i >= 0; i--)
{
t += a[i] * b;
c.insert(c.begin(), t % 10);
t = t / 10;
}
while (t)
{
c.insert(c.begin(), t % 10);
t = t / 10;
}
return c;
}
vector<int> div(vector<int>a, int b)
{
vector<int>c;
bool is_first = true;
int t = 0;
int x = 0;
for (int i = 0; i < a.size(); i++)
{
t = t * 10 + a[i];
x = t / b;
if (!is_first || x)
{
c.push_back(x);
is_first = false;
}
t = t % b;
}
return c;
}
const int N = 10010;
typedef pair<int, int> PII;
PII p[N];
vector<int> max_vector(vector<int>a, vector<int>b)
{
if (a.size() > b.size())return a;
else if (a.size() < b.size())return b;
else
{
for (int i = 0; i < a.size(); i++)
{
if (a[i] > b[i])
return a;
else if (a[i] < b[i])
return b;
}
return a;
}
}
int main()
{
int n;
cin >> n;
int a, b;
cin >> a >> b;//国王左右手
int c, d;
for (int i = 1; i <= n; i++)
{
cin >> c >> d;
p[i].first = c * d;
p[i].second = d;
}
sort(p + 1, p + 1 + n);
vector<int> res;
vector<int>e(1,a);
while (a)
{
res.insert(res.begin(),a % 10);
a = a / 10;
}
for (int i = 1; i < n; i++)
{
res = max_vector(res, div(e, p[i].second));//寻找其中的最大值
e = mul(e, p[i].first / p[i].second);
}
res = max_vector(res, div(e, p[n].second));
for (int i = 0; i < res.size(); i++)
cout << res[i];
cout << endl;
system("pause");
return 0;
}