2020牛客寒假集训营5|2020牛客寒假算法基础集训营5.D——牛牛与牛妹的约会【贪心】
题目传送门
题目描述
牛牛在辛苦的一天的比赛之后,要去找牛妹玩,其实牛妹那天也在比赛。他为了找到牛妹,要尽快的从自己的比赛地到她的比赛地。
还记得吗,比赛地都是只在x轴上的,所以两个人的坐标都满足y=0。牛牛除了可以以1单位距离/单位时间的速度移动任意时间以外,还可以花费1单位时间进行闪现。每次闪现时,如果当前他的坐标是x=k,他将闪现到 x = k 3 x=\sqrt[3]{k} x=3k ? 的位置。
请帮他算算,最短需要多少时间,他可以找到牛妹~
输入描述:
输入数据包括多组用例,输入第一行包含一个数字 T ( 1 ≤ T ≤ 5 × 1 0 5 ) T(1 \leq T \leq 5 \times 10^5) T(1≤T≤5×105),表示数据组数。
接下来T行,每行包括两个整数 a , b ( ∣ a ∣ , ∣ b ∣ ≤ 1 0 6 ) a,b(|a|,|b|\leq 10^6) a,b(∣a∣,∣b∣≤106),表示牛牛所在的位置和牛妹所在的位置。
输出描述:
输出共T行,每行包括一个实数,表示牛牛所花费的最短时间。
如果你的答案是a,标准答案是b,当 ∣ a ? b ∣ ≤ 1 0 ? 6 |a-b|\leq 10^{-6} ∣a?b∣≤10?6 时,你的答案将被判定为正确。
输入
2输出
3 -1
1 2
【2020牛客寒假集训营5|2020牛客寒假算法基础集训营5.D——牛牛与牛妹的约会【贪心】】3.442249570题解
1.000000000
- 贪心找最小代价即可
- 注意正负情况即可
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
const double eps = 1e-7;
int main() {
int T;
cin >> T;
while (T--) {
double a, b;
scanf("%lf%lf", &a, &b);
double ans = 0;
while (1) {
double na = cbrt(a);
// 闪现后的位置
if (fabs(na-b) < fabs(a-b)-1) // 闪现后剩下的距离 < 走1s后剩下的距离。这里不可化简,避免目标点不在左边而在右边
ans += 1.0, a = na;
else {
ans += fabs(a - b);
break;
}
}
printf("%.9f\n", ans);
}
}
推荐阅读
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers
- ZOJ-3447---Doraemon's Number Game (贪心+大数)
- CodeForces 567A Lineland Mail 贪心
- codeforces|Codeforces Round #643 (Div. 2) D. Game With Array (思维,贪心)
- Codeforces Round #643 (Div. 2) B. Young Explorers 题解(贪心)
- CodeForces - 1060D E - Social Circles
- Codeforces Round #503 (by SIS, Div. 2) C. Elections(贪心)
- 贪心|001:特殊密码锁(贪心)
- 贪心|Codeforces D. Solve The Maze (bfs & 贪心) (Round #648 Div.2)