国王游戏贪心算法

/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
typedef pair<int, int>PII;
const int N = 1010;
int n;
PII ps[N];

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 is_first = false;
    for(int i = a.size() - 1, t = 0; i >= 0; i--) 
    {
        t = t * 10 a[i]; 
        int x = t / b;
        if(x || is_first)
        {
            is_first  = true;
            c.push_back(x);
        }
        t %= b;
    }
    return vector<int>(c.rbegin(), c.rend()); 
}

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;
    return b;    
}

void output(vector<int> a)
{
    for(int i = a.size() - 1; i >= 0; i--) cout << a[i];
    cout << endl;
}

int main()
{
    cin >> n;
    for(int i = 0; i <= n; i )
    {
        int a, b;
        cin >> a >> b;
        ps[i] = {a * b, a};
    }
    sort(ps 1, ps n 1);
    
    vector<int>product(1, 1);
    vector<int>res(1,0);
    
    for(int i = 0; i <= n; i )
    {
        if(i) res = max_vec(res, div(product, ps[i].first / ps[i].second));
        product = mul(product, ps[i].second);
    }
    
    output(res);
    return 0;
}

这篇好文章是转载于：学新通技术网