题解 P1080 【国王游戏】

2018-07-05 14:56:39


这道题首先想到需要排序,可是按什么顺序排呢?

这就需要推导了

对于任意一个人i和j,假设i在j前面,i之前所有人的乘积为k1,i~j之间(不包括i,j)的乘积为k2

则此时两人的最大值为max(k1/bi,k1·ai·k2/bj)

如果交换两人的最大值为max(k2/bj,k1·aj·k2/bi)

显然k1·ai·k2/bj>k2/bj,k1·aj·k2/bi>k1/bi

所以如果k1·aj·k2/bi<k1·ai·k2/bj即aj·bj<ai·bi,交换后的最大值就比交换前的最大值小,就需要交换。按照这个比较法sort一下就可以了

剩下的就是枚举1~n,每一个都算一遍取最大。(注意要用高精,打的有点乱。。)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int ans[100000],la=0,res[100000];
struct peo
{
    int a,b;
}p[1100];
bool cmp(peo x,peo y)
{
    return (x.a*x.b)<(y.a*y.b);//按照 两个值的乘积进行排序
}
int m[100000],l=1;
void mutiply(int x)//高精乘法
{
    int add=0;
    for(int i=1;i<=l+10;i++)
    {
        int tmp=m[i]*x+add;
        m[i]=tmp%10;
        add=tmp/10;
    }
    l+=10;
    while(m[l]==0) l--;
}
void get(int x)
{
    memset(res,0,sizeof(res));
    int tmp,l1=0;
    for(int i=l;i>=1;i--)
    {
        tmp=tmp*10+m[i],l1++;
        if(tmp<x) continue;
        res[l1]=tmp/x;
        tmp%=x;
    }//高精除法,注意我存的时候正过来存的,所以还要倒过来一下
    for(int i=1;i<=(l1+1)/2;i++)
        swap(res[i],res[l1-i+1]);
    while(res[l1]==0 && l1>1) l1--;
    //比较大小
    if(l1>la)
    {
        la=l1;
        for(int i=la;i>=1;i--)
            ans[i]=res[i];
    }
    else if(l1==la)
    {
        int f=0;
        for(int i=la;i>=1;i--)
        {
            if(ans[i]<res[i])
            {
                f=1;
                break;
            }
            if(ans[i]>res[i]) break;
        }
        if(f)
        {
            for(int i=la;i>=1;i--)
                ans[i]=res[i];
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        scanf("%d%d",&p[i].a,&p[i].b);
    sort(p+1,p+n+1,cmp);
    m[1]=1;
    for(int i=1;i<=n;i++)
    {
        mutiply(p[i-1].a);
        get(p[i].b);
    }
    if(ans[la]==0) la--;
    for(int i=la;i>=1;i--)
        printf("%d",ans[i]);
    return 0;
}