次元传送门：；洛谷P1080
思路
我们模拟一下只有两个大臣的时候发现
当a1∗b1<a2∗b2是ans1<ans2
所以我们对所有大臣关于左右手之积进行排序
得到最多钱的大臣就是最后一个（当有左手除右手向下取整为0的时候不一定 只有第二个点可以特判）
所以答案用前n-1个人的左手相乘除以第n个人的右手
记得高精
代码
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100010
struct People
{
int l;
int r;
int sum;
}p[maxn];
int n,L=
1;
int g[maxn];
//高精数组
bool cmp(People a,People b)
{
return a.sum<
b.sum;
}
void mul(
int x)
//高精乘法
{
for(
int i=
1;i<=L;i++) g[i]*=p[x].l;
//先乘以每一位
for(
int i=
1;i<=L;i++
)
{
g[i+
1]+=(g[i]/
10);
//进位
g[i]%=
10;
}
L++;
//长度++
while(g[L]>
9)
//延长长度
{
g[L+
1]+=(g[L]/
10);
//计算下一位的进位
g[L]%=
10;
L++;
//长度++
}
if(g[L]==
0) L--;
//清除前导零
}
void div()
//高精除法
{
for(
int i=L;i>=
1;i--
)
{
g[i-
1]+=((g[i]%p[n].r)*
10);
//计算下一位
g[i]/=
p[n].r;
}
while(g[L]==
0) L--;
//清除前导零
if(L==
0) cout<<
1;
//如果减完了就输出1 第二个测试点特判
}
int main()
{
cin>>n>>p[
0].l>>p[
0].r;
//国王不用排序
for(
int i=
1;i<=n;i++
)
{
cin>>p[i].l>>
p[i].r;
p[i].sum=p[i].l*p[i].r;
//计算左右手相乘
}
sort(1+p,
1+p+n,cmp);
//排序
g[
1]=p[
0].l;
//初始化高精
for(
int i=
1;i<n;i++) mul(i);
//乘以前n-1个人的左手
div();
//除以第n个人的右手
for(
int i=L;i>=
1;i--) cout<<g[i];
//倒序输出
}
转载于:https://www.cnblogs.com/BrokenString/p/9888087.html
