#8#9 TLE 已经写晕了,求大佬帮忙优化一下
查看原帖
#8#9 TLE 已经写晕了,求大佬帮忙优化一下
33364
summeray楼主2024/4/3 03:02
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>

using namespace std;

class High_Pre_Cal
{
    private:
        vector <int> A;
    public:
        High_Pre_Cal(/* args */);
        ~High_Pre_Cal();

        void Read();
        void Write();
        void Get(int a);
        void Mul(int a);
        void Div(int a);
        int Get_Digit(int k);
        int Length();
};

High_Pre_Cal::High_Pre_Cal(/* args */)
{
}

High_Pre_Cal::~High_Pre_Cal()
{
    A.clear();
}

void High_Pre_Cal::Read()
{
    string s;
    cin >> s;
    for(int i = s.length() - 1; i >= 0; --i)
    {
        A.push_back(s[i] - '0');
    }
}

void High_Pre_Cal::Write()
{
    for(int i = A.size() - 1; i >= 0; --i)
    {
        cout << A[i];
    }
    cout << endl;
}

void High_Pre_Cal::Get(int a)
{
    string s = to_string(a);
    for(int i = s.length() - 1; i >= 0; --i)
    {
        A.push_back(s[i] - '0');
    }
}

void High_Pre_Cal::Mul(int a)
{
    int t = 0;

    for(unsigned int i = 0; i < A.size(); ++i)
    {
        A[i] *= a;
        A[i] += t;
        t = A[i] / 10;
        A[i] %= 10;
    }

    while(t)
    {
        A.push_back(t % 10);
        t /= 10;
    }
}

void High_Pre_Cal::Div(int a)
{
    int r = 0;
    vector <int> C;

    for(int i = A.size() - 1; i >= 0; --i)
    {
        r = r * 10 + A[i];
        C.push_back(r / a);
        r %= a;
    }

    reverse(C.begin(), C.end());

    for(int i = C.size() - 1; i > 0; --i)
    {
        if(C[i] == 0)
        {
            C.pop_back();
        }
        else
        {
            break;
        }
    }

    A = C;
}

int High_Pre_Cal::Get_Digit(int k)
{
    return A[k];
}

int High_Pre_Cal::Length()
{
    return A.size();
}

bool High_Pre_Camp(High_Pre_Cal A, High_Pre_Cal B)
{
    if(A.Length() != B.Length())
    {
        return A.Length() > B.Length();
    }
    else
    {
        for(int i = A.Length() - 1; i >= 0; ++i)
        {
            if(A.Get_Digit(i) > B.Get_Digit(i))
            {
                return true;
            }
        }

        return false;
    }
}

class Minister
{
    private:
        int a, b;
        High_Pre_Cal Prize;
    public:
        Minister(/* args */);
        ~Minister();

        void Put_Num(int x, int y);
        int Get_Mul();
        void Put_Prize(High_Pre_Cal A);
        int Get_A();
        int Get_B();
        High_Pre_Cal Get_Prize();
};

Minister::Minister(/* args */)
{
}

Minister::~Minister()
{
}

void Minister::Put_Num(int x, int y)
{
    a = x;
    b = y;
}

int Minister::Get_Mul()
{
    return a * b;
}

int Minister::Get_A()
{
    return a;
}

int Minister::Get_B()
{
    return b;
}

void Minister::Put_Prize(High_Pre_Cal A)
{
    Prize = A;
}

High_Pre_Cal Minister::Get_Prize()
{
    return Prize;
}

Minister M[1005];
Minister K;

void Input_Data(int n)
{
    int x, y;
    cin >> x >> y;
    K.Put_Num(x, y);

    for(int i = 1; i <= n; ++i)
    {
        cin >> x >> y;
        M[i].Put_Num(x, y);
    }
}

void Output_Data(int n)
{
    int x, y;
    High_Pre_Cal p;

    cout << n << endl;
    x = K.Get_A();
    y = K.Get_B();
    cout << x << " " << y << endl;

    for(int i = 1; i <= n; ++i)
    {
        x = M[i].Get_A();
        y = M[i].Get_B();
        p = M[i].Get_Prize();
        cout << x << " " << y << endl;
        p.Write();
    }
}

void OutPut_Data(Minister M_2[], int n)
{
    int x, y;
    High_Pre_Cal p;

    cout << n << endl;
    x = K.Get_A();
    y = K.Get_B();
    cout << x << " " << y << endl;

    for(int i = 1; i <= n; ++i)
    {
        x = M_2[i].Get_A();
        y = M_2[i].Get_B();
        p = M_2[i].Get_Prize();
        cout << x << " " << y << endl;
        p.Write();
    }
}

bool Camp(Minister A, Minister B)
{
    return A.Get_Mul() < B.Get_Mul();
}

High_Pre_Cal Calculate_Prize(Minister M_1[], int k)
{
    High_Pre_Cal A;

    //OutPut_Data(M_1, k);//

    A.Get(K.Get_A());
    //A.Write();//
    for(int i = 1; i < k; ++i)
    {
        A.Mul(M_1[i].Get_A());
        //A.Write();//
    }
    A.Div(M_1[k].Get_B());
    //cout << M_1[k].Get_B() << " ";//
    //A.Write();//

    return A;
}

void Real_Work()
{
    int n;
    cin >> n;
    Input_Data(n);

    //Output_Data(n);//
    //OutPut_Data(M, n);//

    sort(M + 1, M + n + 1, Camp);

    //Output_Data(n);//

    for(int i = 1; i <= n; ++i)
    {
        High_Pre_Cal X = Calculate_Prize(M, i);
        //cout << "No." << i << " ";//
        //X.Write();//
        M[i].Put_Prize(X);
    }

    //OutPut_Data(M, n);//

    High_Pre_Cal Max;
    Max.Get(0);
    for(int i = 1; i <= n; ++i)
    {
        if(High_Pre_Camp(M[i].Get_Prize(), Max))
        {
            Max = M[i].Get_Prize();
        }
    }

    Max.Write();
}

int main()
{
    Real_Work();
    
    return 0;
}
2024/4/3 03:02
加载中...