链接:https://ac.nowcoder.com/acm/contest/3006/D
来源:牛客网
题目描述: 牛牛在辛苦的一天的比赛之后,要去找牛妹玩,其实牛妹那天也在比赛。他为了找到牛妹,要尽快的从自己的比赛地到她的比赛地。
还记得吗,比赛地都是只在xxx轴上的,所以两个人的坐标都满足y=0。牛牛除了可以以111单位距离/单位时间的速度移动任意时间以外,还可以花费1单位时间进行闪现。每次闪现时,如果当前他的坐标是x=k,他将闪现到x= k 3 \sqrt[3]{k} 3k ?的位置。
请帮他算算,最短需要多少时间,他可以找到牛妹~
输入描述: 输入数据包括多组用例,输入第一行包含一个数字T(1≤T≤5×105),表示数据组数。
接下来T行,每行包括两个整数a,b(∣a∣,∣b∣≤106),表示牛牛所在的位置和牛妹所在的位置。
输出描述: 输出共T行,每行包括一个实数,表示牛牛所花费的最短时间。
如果你的答案是a,标准答案是b,当∣a?b∣≤10?6时,你的答案将被判定为正确。
输入样例:
2
3 -1
1 2
输出样例:
3.442249570
1.000000000
核心思想: 闪现到x= k 3 \sqrt[3]{k} 3k ?,意味着闪现只能向原点靠近,所以两种操作的出现顺序只能是以下几种情况:
1、只使用闪现
2、只使用基础位移
3、先使用若干次闪现,再使用若干次基础位移。
【牛客3006D-牛牛与牛妹的约会-思维】所以,我们只需要先使用闪现,直到闪现的收益不如基础位移,就改用基础位移。
注意:pow函数的底数不允许为负数,分类讨论一下。
代码如下:
#include
#include
#include
using namespace std;
typedef long long ll;
bool pd(double a,double b)
{
if(a>=0)
{
if(fabs(pow(a,1.0/3)-b)>T;
while(T--)
{
scanf("%lf%lf",&a,&b);
ans=0;
while(pd(a,b))
{
if(a>=0)
a=pow(a,1.0/3);
else
a=-pow(-a,1.0/3);
ans++;
}
ans+=fabs(a-b);
printf("%.9f\n",ans);
}
return 0;
}
推荐阅读
- 每日一题|每日一题-解码(第十一届蓝桥杯)(简单思维)
- codeforces|Codeforces Round #665 (Div. 2) A. Distance and Axis(思维,数学)
- codeforces|Codeforces Global Round 10 C. Omkar and Waterslide(思维)
- codeforces|Codeforces Global Round 10 D. Omkar and Bed Wars(思维,分块)
- codeforces|Codeforces Round #643 (Div. 2) D. Game With Array (思维,贪心)
- codeforces|Codeforces Round #648 (Div. 2) C. Rotation Matching(思维)
- CodeForces - 245C Game with Coins
- Codeforces Round #643 (Div. 2) C. Count Triangles 题解(思维)
- #|C. Choosing flowers(枚举+思维+二分)
- #|A. Distance and Axis(思维) Codeforces Round #665 (Div. 2)