国王游戏

题目描述

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

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

输入输出格式

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

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

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

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

思路

贪心

按照左右手的乘积为第一关键字,左手大小为第二关键字,进行排序

证明:

假设我们只考虑两个人的关系,之前,以及之后都按照最优策略排序

那么,之前所有人的左手上的数的乘积是一定的:这两个人,对之后的影响—即这两个人的左手乘积也是一样的,那么只要保证这两个人的先后顺序最优,则整个队列都可以最优,所以我们只考虑这两个人

设之前所有的的左手乘积为s,那么:

1,假定A排在B之前

可知Aget1=s/ra,Bget1=s*la/rb

2,假定B排在A之前 可知Aget2=s*lb/ra,Bget2=s/rb

如果我们在这两种选择中取最优方案,那么这四个值的最大值应当是最小的,所以我们只考虑最大值就可以了—显然Aget1<Aget2,Bget2<Bget1,所以我们只要考虑Aget2与Bget1就好了

如果Aget2>Bget1,那么我们要使A排在B前,取Bget1作为最大值,此时: slb/ra>sla/rb –> slbrb>slara –> lbrb>lara

同理,当Aget2<Bget1时,可得: lbrb<lara,此时B在A之前

所以,左手右手乘积较大的人,要排在后面 至于左手大小…这个有没有都行,反正就是习惯一打…..

代码 (高精!)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
struct pepo
{
    int l,r;
    int that;
} a[1010];
int now[1000000],tot[1000000],tw;
int n;
int ans[1000000];
bool comp(pepo a,pepo b)
{
    if(a.that==b.that) return a.l<b.l;
    return a.that<b.that;
}
void gjc(int a)//now=tot/a
{
    int yw=tw;
    int pre=0;
    while(yw!=0)
    {
        now[yw]=(tot[yw]+pre*10)/a;
        pre=(tot[yw--]+pre*10)%a;
    }
    yw=tw;
    while(ans[yw]==now[yw]) yw--;
    int fl=ans[yw]>now[yw] ? 0:1;
    if(fl) memcpy(ans,now,sizeof(now));
}
void ggc(int a)//tot*=a
{
    int jinwei=0;
    for(int i=1;i<=tw;++i)
    {
        int tt=tot[i];
        tot[i]=(tot[i]*a+jinwei)%10;
        jinwei=(tt*a+jinwei)/10;
    }
    while(jinwei)
    {
        tot[++tw]=jinwei%10;
        jinwei/=10;
    }
}//yes
int main()
{
//    freopen("game.in","r",stdin);
//    freopen("game.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<=n;++i)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].that=a[i].l*a[i].r;
    }
    sort(a+1,a+n+1,comp);
    while(a[0].l)
    {
        tot[++tw]=a[0].l%10;
        a[0].l/=10;
    }
    for(int i=1;i<=n;++i)
    {
        gjc(a[i].r);
        ggc(a[i].l);
    }
    int fl=1;
    for(int i=tw;i>=1;--i)
    {
        if(ans[i]==0&&fl) continue;
        else
        {
            printf("%d",ans[i]);
            fl=0;
        }
    }
    return 0;
}
(update the code to your comment plugin in comment-full.html)