P1080 国王游戏

题解

贪心策略：按照大臣左右手数字乘积从小到大排序

假设我们已经把大臣排了一个顺序

假定在这个顺序下我们可以保证得到奖赏最多的大臣所得奖赏最少

那么我们一旦交换任意两个大臣，得到奖赏最多的大臣所得奖赏就不是最少的

假设 3,4 号大臣是候选 “ 所得奖赏最多的大臣 ” ，那么我们现在交换他们的顺序

交换之后 3,4 之前的大臣以及3,4之后的大臣所得奖赏都不会被影响，受到影响的只是3,4号大臣

那么我们设3,4之前的大臣左手上的乘积和为 S

所以，

对于交换前：ans1 = max( s / b[3] , s * a[3] / b[4] )

对于交换后：ans2 = max( s / b[4] , s * a[4] / b[3] )

由于交换后无法得到更优解，所以

ans1 < ans2

max( s / b[3] , s * a[3] / b[4] ) < max( s / b[4] , s * a[4] / b[3] )

max( 1 / b[3] , 1 * a[3] / b[4] ) < max( 1 / b[4] , 1 * a[4] / b[3] )

所以答案只和第2,4项有关

a[3] / b[4] < a[4] / b[3]

移项

a[3] * b[3] < a[4] * b[4]

所以：

贪心策略：按照大臣左右手数字乘积从小到大排序

剩下的问题就是高精度处理了QWQ

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<queue>

using namespace std;

#define ll long long

inline int read()

{

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n;

long long ans;

struct node

{

    int a,b;

    long long val;

    long long mul;

}peo[];

bool cmp(node x,node y)

{

    return x.mul <y.mul ;

}

int main()

{

    n=read();

    for(int i=;i<=n;i++)

    {

        peo[i].a =read();

        peo[i].b =read();

        peo[i].mul =peo[i].a *peo[i].b ;

    }

    sort(peo+,peo+n+,cmp);

    for(int i=;i<=n;i++)

    {

        long long res=;

        for(int j=;j<i;j++)

          res*=peo[j].a ;

        res/=peo[i].b ;

        ans=max(ans,res);

    }

    printf("%lld\n",ans);

    return ;

}

60' 没加高精度

巴特西

P1080 国王游戏（等待高精度AC）

P1080 国王游戏

最新文章

热门文章

巴特西

P1080 国王游戏 （等待高精度AC）

P1080 国王游戏

最新文章

热门文章

P1080 国王游戏（等待高精度AC）