【NOIP 2012】国王游戏

2024-04-03 10:33:52

题目描述

恰逢 $ H$ 国国庆，国王邀请 $ n $ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入输出格式

输入格式：

第一行包含一个整数 $n$ ，表示大臣的人数。

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

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

输出格式：

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

输入输出样例

输入样例#1：

输出样例#1：

分析

方法：贪心+高精

那么究竟是按照$a$还是$b$排序呢？

假设有$2$个大臣，分别是$1$和$2$，那么他们得到的金币分别是$\frac{a_0}{b_1}$和$\frac{a_0*a_1}{b_2}$，对于这种顺序，我们记答案为$ans_1$，则有

\[ans_1=max(\frac{a_0}{b_1},\frac{a_0*a_1}{b_2})\]

我们将这两个大臣交换一下位置，答案记为$ans_2$，则有

\[ans_2=max(\frac{a_0}{b_2},\frac{a_0*a_2}{b_1})\]

易知$\frac{a_0}{b_1}<\frac{a_0*a_2}{b_1}$和$\frac{a_0}{b_2}<\frac{a_0*a_1}{b_2}$，若$ans_1<ans_2$，即有

\[\frac{a_0*a_1}{b_2}<\frac{a_0*a_2}{b_1}\]

变形得

\[a_1*b_1<a_2*b_2\]

为了使$ans$最小，所以我们以$a_i*b_i$从小到大排序。

最后，这题需要使用高精，但因为我太菜了，不会打高精，所以高精部分参考了~~(抄)~~了这位大佬的题解

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define il inline
#define re register
#define maxn 10007
#define mymax(a,b) a>b?a:b
#define mymin(a,b) a<b?a:b
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;

template<typename T>inline void read(T &x){
    T f=1;x=0;char c;
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+(c^48);
    x*=f;
}

struct king{
    int a,b,cp;
}kd[maxn];

struct overload{
    int data[maxn];
    overload(){
        memset(data,0,sizeof(data));
        data[0]=1;
    }
    overload(int x){
        memset(data,0,sizeof(data));
        data[0]=1;
        int i=1;
        while(x){
            data[i++]=x%10;
            x/=10;
        }
        data[0]=--i;
    }
    overload operator * (const int &x){
        overload y;
        int len;
        y.data[0]=data[0];
        for(int i=1;i<=data[0];++i) y.data[i]=data[i]*x;
        for(int i=1;i<=y.data[0]||y.data[i];len=++i){
            y.data[i+1]+=y.data[i]/10;
            y.data[i]%=10;
        }
        y.data[len] ? y.data[0]=len : y.data[0]=--len;
        return y;
    }
    overload operator / (const int &x){
        overload y;
        y.data[0]=data[0];
        int rest=0;
        for(int i=data[0];i;--i){
            rest=rest*10+data[i];
            y.data[i]=rest/x;
            rest%=x;
        }
        while(!y.data[y.data[0]]&&y.data[0]>1) y.data[0]--;
        return y;
    }
    bool operator < (const overload &x)const{
        if(data[0]==x.data[0]){
            int i=data[0];
            while(data[i]==x.data[i]&&i>1) i--;
            if(i) return data[i]<x.data[i];
            else return false;
        }
        else return data[0]<x.data[0];
    }
};
ostream& operator << (ostream& out,const overload &x){
    for(int i=1;i<=x.data[0];++i) out << x.data[x.data[0]-i+1];
    return out;
}

int n;
overload ans;

bool cmp(king x,king y){
    return x.cp<y.cp;
}

int main(){
    read(n);
    for(int i=0;i<=n;++i) read(kd[i].a),read(kd[i].b),kd[i].cp=kd[i].a*kd[i].b;
    sort(kd+1,kd+1+n,cmp);
    overload k(1);
    for(int i=1;i<=n;++i){
        overload tmp;
        k=k*kd[i-1].a;
        tmp=k/kd[i].b;
        if(ans<tmp) ans=tmp;
    }
    cout<<ans;
    return 0;
}

码农公寓