luogu的忠实支持者

比较有名的贪心题，培训时经常遇到，只是由于涉及到了高精除，一直懒得写。今日将他整理出来

首先是贪心策略

设a，b两个人进行贪心的排序（解决了两个人的排序方式，就解决了全部人的排序方式，只需要重载运算符或写成函数传进stl中就行了）设a，b前面的人都是最优的且一样，左手乘积为dplan 1：a在b前面最大值=max（d/a的右手，d*a的左手/b的右手）plan 2：b在a前面最大值=max（d/b的右手，d*b的左手/a的右手）可以明显地看出d/a的右手始终小于d*b的左手/a的右手同理也b是一样所以答案就是在d*b的左手/a的右手，d*a的左手/b的右手中选出两边共同约去d这样贪心规则就出来了

上代码

#include
    
     #include
     
      #include
      
       using namespace std;struct node{    int x;    int y;}m[1001];bool compare(const node &h1,const node &h2){    return h1.x*h1.y
       
        0)//高精除低精除法    {        now=now*10+cheng[i];        pass[i]=now/m[x].y;        now=now%m[x].y;        i--;    }    tailp=tail;    while(pass[tailp]==0&&tailp)    //更改长度            tailp--;}void max(){    bool exchange=false;//是否交换的flag    if(taila
        
         =1;i--)        {            if(pass[i]>ans[i])            {                exchange=true;                break;            }            if(pass[i]
         
          =1;i--) ans[i]=pass[i]; taila=tailp; } return ;}void mul(int x){ int p=0; for(int i=1;i<=tail;i++) { cheng[i]=cheng[i]*m[x].x+p; p=cheng[i]/10; cheng[i]%=10; } while(p)//p有可能不是一位数 { cheng[++tail]=p%10; p/=10; }}int main(){ //cin.sync_with_stdio(false); int n; cin>>n; int a,b; scanf("%d %d",&a,&b); for(int i=1;i<=n;i++) scanf("%d %d",&m[i].x,&m[i].y); sort(m+1,m+1+n,compare); while(a)//将国王的左手转换成高精度储存 { cheng[++tail]=a%10; a/=10; } for(int i=1;i<=n;i++) { div(i);//高精除低精 max();//比较，因为有可能最后一个不是最大的 mul(i);//高精度乘法，当然是低精 } for(int i=taila;i>=1;i--) printf("%d",ans[i]);//输出 return 0;}