题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 1010
typedef pair<int,int> PII;
PII info[N];


vector<int> mul(vector<int> a,int b) //大整数*小整数的乘法
{
    int i,carry;
    vector<int> ret;
    carry=0;
    for(i=0;i<a.size();i++)
    {
        ret.push_back((a[i]*b+carry)%10);
        carry=(a[i]*b+carry)/10;
    }

    while(carry!=0)
    {
        ret.push_back(carry%10);
        carry=carry/10;
    }
    return ret;
}

vector<int> divide(vector<int> a,int b) //大整数/小整数的除法
{
    int re=0,i,t;
    vector<int> ret;
    bool tag=false;  //判断是否非最高位0
    for(i=a.size()-1;i>=0;i--)  //从高位到低位遍历被除数的每一位
    {
        re=re*10+a[i];
        t=re/b;
        if(t!=0||tag==true)
        {
            tag=true;
            ret.push_back(t);
        }
        re=re%b;
    }

    reverse(ret.begin(),ret.end());  //反转商的高位和低位，使商从低位开始存储
    return ret;
}

vector<int> maxvalue(vector<int> a,vector<int> b)
{
    int i;
    if(a.size()>b.size())
    {
        return a;
    }
    else if(a.size()<b.size())
    {
        return b;
    }
    else
    {
        /*if(vector<int>(a.rbegin(),a.rend())>vector<int>(b.rbegin(),b.rend())) //如果a、b的位数相等则从高位到低位比较数字的每一位
        {
            return a;
        }
        return b;*/
        for(i=a.size()-1;i>=0;)
        {
            if(a[i]>b[i])
            {
                return a;
            }
            else if(a[i]<b[i])
            {
                return b;
            }
            else
            {
                i--;
            }
        }
        return a; //如果a和b的每一位都相等，则a==b此时返回a、b均可
    }
}
int main()
{
    vector<int> product(1,1);
    vector<int> res(1,0);
    int n,i,l,r;
    cin>>n;
    for(i=0;i<=n;i++)
    {
        cin>>l>>r;
        info[i].first=l*r;
        info[i].second=l;
    }
    sort(info+1,info+n+1); //按照first从小到大排序
    for(i=0;i<=n;i++)
    {
        if(i!=0)
        {
            res=maxvalue(res,divide(product,info[i].first/info[i].second));
        }
        product=mul(product,info[i].second);  //累乘
    }

    for(i=res.size()-1;i>=0;i--)  //从高位到低位输出最大值的结果
    {
        cout<<res[i];
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla