【问题描述】

Alice和Bob在玩游戏。他们一共玩了t轮游戏。游戏中,他们分别获得了n个和m个小球。每个球上有一个分数。每个人的得分都为他所获得所有小球分数的乘积,分数小者获胜。问没轮游戏谁会获胜?请输出每轮游戏的胜者。数据保证不会出现平局,且两个人分数差异大于任意一个人分数的1%。

【输入格式】

第一行为两人玩的轮数t(1≤t≤10)

每一轮的游戏输入中:

第一行一个整数n,代表Alice获得球的个数。

第二行为n个整数ai,代表Alice每个球的分数。

第三行为一个整数m,代表Bob获得球的个数。

第四行为m个整数bi,代表Bob每个球的分数。

【输出格式】

输出共t行,每行为该轮胜者的名字“Alice”或者“Bob”。

【输入样例】

1

3

2 3 4

4

1 3 4 5

【输出样例】

Alice

【样例说明】

Alice:2×3×4=24

Bob:1×3×4×5=60

【数据范围】

对于100%的数据范围 1≤n,m≤100000,-10000≤ai,bi≤10000

看起来要用高精度的样子……可惜会T掉。

实际上,用double控制一下精度足矣。比大小,首先把符号什么的都判定过后全部取正值来计算。

直接用Bob/Alice的值来确定胜者,定义两个指针一个指向Bob一个指向Alice

为了计算Bob/Alice 我们可以先对球全部排序(作用等会儿讲) 之后只要sum>=1就先除Alice知道<=1再乘上Bob

这样做之后sum可以维持在1左右不会爆精度,并且经过这个过程之后某一个序列一定会被算完。

假设算完的是Alice 那么就一直乘上Bob 此时sort的优势就来了,因为序列单增,当你乘到>1的时候其实就不需要再乘了,因为后面单增,肯定还是>1的。算完的是Bob也一样,这样避免了可以用很大的数卡掉这个算法的Bug。

当然,实现时我控制精度是在1e-5~1e5的。

下面是代码:

 

本文为原创文章,唯一地址链接:【Ball】 转载请注明转自 stdKonjac

我来吐槽

*

*

取消

*