洛谷P2694 接金币

url : https://www.luogu.com.cn/problem/P2694

tag:
模拟

思路:
为了可以接到所有的金币,所以我们可以采取一个贪心的策略,每次都先去接高度距离自己最近的一个金币,之后判断在这个过程中是否存在接不到的情况,如果有就说明接不到所有的金币,否则就是可以接到所有的金币。
为了采取贪心的策略,我们需要对所有的金币按照高度排序。然后需要维护一个全局的掉落高度 ey 和自己的位置 fx ,之后按照高度遍历每一个金币,判断,当我走到这个金币的时候金币到我的高度,如果大于等于0则说明可以接到,否则接不到。如果可以接到,则更新一下ey和fx。
关于如何排序,可以利用pair的特性,即先按照first排序如果一样再按照second排序,来排。所以我们可以用pair来存每一个金币的位置,且将高度放到first。
关于如何判断,因为题目有给一个速度都是1,所以移动的距离(用绝对值表示)就是这一段时间,即从原来我的位置到要接的那个金币下面的时间,金币下降的高度。所以先让 ey += abs(fx - dp[i].second),之后再判断 dp[i].first - ey 的大小。如果大于0就可以接到,小于零就break掉。
当大于0时,为了可以接到,所以必须让金币的高度为0,因此就还要等一段时间,这段时间fx不会更新,但是ey需要再加上 dp[i].first - ey, 表示在等待的过程中全局的下降距离增加的距离。
ps:如果速度不为1可能反而会好理解一点。

代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. typedef pair<int, int> PII;
  5. PII dp[52];
  6. int main()
  7. {
  8. int g;
  9. cin >> g;
  10. while(g--)
  11. {
  12. int n;
  13. bool flag = true;
  14. cin >> n;
  15. int fx = 0, ey = 0;
  16. for (int i = 0; i < n; i ++)
  17. {
  18. cin >> dp[i].second >> dp[i].first;
  19. }
  20. sort(dp, dp + n);
  21. for (int i = 0; i < n; i ++)
  22. {
  23. ey += abs(fx - dp[i].second);
  24. if (dp[i].first - ey >= 0)
  25. {
  26. ey += dp[i].first - ey;
  27. fx = dp[i].second;
  28. }
  29. else
  30. {
  31. flag = false;
  32. cout << "Notabletocatch\n";
  33. break;
  34. }
  35. }
  36. if (flag) cout << "Abletocatch\n";
  37. }
  38. return 0;
  39. }
添加新评论