题目描述

恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。

首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。

然后,让这 n 位大臣排成一排,国王站在队伍的最前面。

排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:

排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。

注意,国王的位置始终在队伍的最前面。

输入格式
第一行包含一个整数 n,表示大臣的人数。

第二行包含两个整数 a 和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。

接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。

输出格式
输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

数据范围
$1≤n≤1000$
$0<a,b<10000$

样例

输入样例：
3
1 1
2 3
7 4
4 6
输出样例：
2

贪心+排序+高精度

这道题目,我们容易想到一种错误的做法,就是将左手的数字从小到大排序,然后再排序右手上的数,从小到大排序,这个其实是错误的贪心做法,因为我们很容易举出反例,比如说.

1 7
2 3

和

2 3
1 7

明显的是,后面的更加最优,因此我们需要按照,每个大臣左手和右手的乘积来从小到大排序,具体证明方法,大致是利用微扰(邻项交换)证明,具体过程看《算法竞赛进阶指南》

还要注意,国王的位置队列最前面,而且不参与排序.

高精度让这道题目恶心了许多,因此我们需要熟记高精度的bign板子.

精简代码

#include <bits/stdc++.h>
using namespace std;
#define vint vector<int> 
const int N=1100;
struct node
{
    int l,r;
} a[N];
int n,m,i,j,k;
vint now,ans;
void out(vint ans)
{
    for(int i=0;i<ans.size();i++)
        cout<<ans[i];
    cout<<endl;
}
int cmp(node a,node b)
{
    if (a.l*a.r==b.l*b.r)
        return a.r<b.r;
    return a.l*a.r<b.l*b.r;
}
vint max_2(vint a,vint b)
{
    if (a.size()!=b.size())
        return a.size()>b.size()?a:b;
    return a>b?a:b;
}
vint mul(vint a,int x)
{
    reverse(a.begin(),a.end());
    for(int i=0;i<a.size();i++)
        a[i]*=x;
    for(int i=0;i<a.size();i++)
    {
        if (i<a.size()-1)
            a[i+1]+=a[i]/10;
        else if (a[i]>=10)
            a.push_back(a[i]/10);
        a[i]%=10;
    }
    reverse(a.begin(),a.end());
    return a;
}
vint dis(vint a,int x)
{
    vint c;
    int ok=true,s=0;
    for(int i=0;i<a.size();i++)
    {
        s=s*10+a[i];
        if(!ok || s>=x)
        {
            ok=false;
            c.push_back(s/x); 
        }
        s%=x;
    }
    return c;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<=n;i++)
        cin>>a[i].l>>a[i].r;
    sort(a+1,a+1+n,cmp);
    now.push_back(1);
    for(int i=1;i<=n;i++)
    {
        now=mul(now,a[i-1].l);
        ans=max_2(ans,dis(now,a[i].r));
    }
    out(ans);
    return 0;
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=10100;
#define mk(a,b) make_pair<int,int>(a,b)
#define ll long long
#define Pll pair<ll,ll>
#define for_up(a,b,c) for (int a=b;a<=c;a++)
struct int_l
{
    int data[N];
    int_l()  
    {
        memset(data, 0, sizeof(data));
        data[0] = 1;
    }
    int_l(int x)    
    {
        memset(data, 0, sizeof(data));
        data[0] = 1;
        int i = 1;
        while (x)
        {
            data[i++] = x % 10;
            x /= 10;
        }
        data[0] = --i;
    }
    int_l operator *(const int &x)  
    {
        int_l a;
        int len;
        a.data[0] = data[0];
        for_up(i, 1, data[0]) a.data[i] = data[i] * x;
        for (int i = 1; i <= a.data[0] || a.data[i]; len = ++i)
        {
            a.data[i + 1] += a.data[i] / 10;
            a.data[i] %= 10;
        }
        a.data[len] ? a.data[0] = len : a.data[0] = --len;
        return a;
    }
    int_l operator /(const int &x)   
    {
        int_l a;
        a.data[0]=data[0];
        int rest = 0;
        for (int i = data[0]; i >= 1; i--)   
        {
            rest = rest * 10 + data[i];
            a.data[i] = rest / x;
            rest %= x;
        }
        while (!a.data[a.data[0]] && a.data[0]>1) a.data[0]--; 
        return a;
    }
    bool operator <(const int_l &x)const 
    {
        if(data[0]==x.data[0])  
        {
            int i;
            for(i=data[0]; data[i]==x.data[i] && i > 1; i--); 
            if(i >= 1) return data[i] < x.data[i];
            else return false;
        }
        else return data[0] < x.data[0];
    }
};
ostream& operator << (ostream& out, const int_l &x)
{
    for_up(i, 1, x.data[0]) out << x.data[x.data[0] - i + 1];
    return out;
}

Pll a[N];
int c[N],n;
int cmp(Pll a,Pll b)
{
    if (a.first*a.second==b.first*b.second)
        return a.first<b.first;
    return a.first*a.second<b.first*b.second;
} ;
int main()
{
//  freopen("stdin.in","r",stdin);
//  freopen("stdout.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n;
    for_up(i,0,n)
    cin>>a[i].first>>a[i].second;
    sort(a+1,a+1+n,cmp);
    int_l x=1,ans=0,sm=0;
    for_up(i,1,n)
    {
        if(a[i-1].first==0) 
            break;
        x=x*a[i-1].first;
        if (a[i].second==0)
            break;
        sm=x/a[i].second;
        if (ans<sm)
            ans=sm;
    }
    cout<<ans;
    return 0;
}