解题思路：（经典贪心之-----使最大值最小，且因该题的数据范围故应使用高精度乘法，高精度除法）
贪心思路的证明：
假设相邻的两个人左右手分别是(a, b), (A, B)。假设a * b <= A * B，i之前所有人的左手乘积为S。
则，ans1 = max{S / b, S * a / B}
若交换（a,b),(A,B) 的顺序
则，ans2 = max{S / B, S * A / b}
因为，a * b <= A * B
所以，S * a / B <= S * A / b
又因为，S / B <= S * a / B
所以，ans2 = S * A / b
ans1 = max{S / b, S * a / B}
所以，ans1 <= ans2
所以贪心策略应按照每个大臣左右手数字乘积的升序来排列
注：高精度算法
代码：
我要评论#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <iterator>
#include<math.h>
#define debug() puts("what the fuck")
#define ll long long
#define INF 0x3f3f3f3f //无穷大
const int maxn=8000009;
const double pi = acos(-1.0); //π的大小
using namespace std;
vector<int> mul(vector<int>a,int b) //高精度乘法
{
vector<int>c;
int t=0;
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(vector<int>a,int b) //高精度除法
{
vector<int> c;
bool flag=true;
int t=0;
for(int i=a.size()-1; i>=0; i--)
{
t=t*10+a[i];
int x=t/b;
if(!flag||x)
{
flag=false;
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(a.size()<b.size())
return b;
if(vector<int>(a.rbegin(),a.rend())>vector<int>(b.rbegin(),b.rend()))
return a;
else
return b;
}
struct Node
{
int l,r;
} n[20000];
bool cmp(Node a,Node b)
{
return a.l*a.r<b.l*b.r;
}
int main()
{
int p;
cin>>p;
for(int i=0; i<=p; i++)
{
cin>>n[i].l>>n[i].r;
}
sort(n+1,n+1+p,cmp);
vector<int>a(1,1);
vector<int>res(1,0);
for(int i=0; i<=p; i++)
{
if(i!=0)
res=max_vec(res,div(a,n[i].r));
a=mul(a,n[i].l);
}
for(int i=res.size()-1; i>=0; i--)
cout<<res[i];
cout<<endl;
return 0;
}
本文地址：https://blog.csdn.net/weixin_45797752/article/details/107895830
如对本文有疑问， 点击进行留言回复！！
网友评论