题目链接:https://ac.nowcoder.com/acm/contest/5674/K
题目大意:
有一个土拨鼠在节点1,一个橘子在节点n,在t时刻之前土拨鼠向着n走,橘子不动,从t时刻开始,橘子开始抓土拨鼠,土拨鼠开始跑,土拨鼠 1m/s, 橘子 2m/s,问还有多长时间橘子才能抓到土拨鼠。
解题思路:
幸好是一个直线运动,没有二维的考虑。
首先要求的 t 时刻土拨鼠的位置,然后土拨鼠需要逃跑,所以得与 n 点背向而跑,这时候有俩种可能
1.土拨鼠可以跑的路很长,orange抓到它也没跑到尽头。
2.土拨鼠可以跑的路很短,土拨鼠跑到路的尽头等待orange来抓它
所以得求土拨鼠能跑的最远距离, 而且因为背向而跑的,所以用相对运动的来做,他们的相对速度为1m/s,所以orange追上土拨鼠需要花费的时间,就是相对距离。
有点绕逻辑,其实主要是英文...
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<cstring> #include<cmath> using namespace std; const int N = 1e5 + 5; struct node{int to;}; vector <node> G[N]; int d_hog[N], orange[N], f[N]; void dfs(int u, int fa, int d[]) { f[u] = fa; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].to; if (v == fa) continue; d[v] = d[u] + 1; dfs(v, u, d); } } void dfs2(int u, int fa, int &maxx) { maxx = max(maxx, orange[u]); for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].to; if (v == fa) continue; dfs2(v, u, maxx); } } int main() { int n, t; memset(d_hog, 0, sizeof(d_hog)); memset(orange, 0, sizeof(orange)); scanf("%d %d", &n, &t); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); G[u].push_back({v}); G[v].push_back({u}); } dfs(n, n, orange); //遍历organge是希望fa保存orange的父节点 int hog_start = 1; while (t--) { //从1向上寻找t次,找到t秒候hog应该在的位置 hog_start = f[hog_start]; } int maxx = 0; dfs2(hog_start, f[hog_start], maxx); //求得hog背离n点而行能走的最大距离(这个距离是以n点位参考点) int max_dis = maxx - orange[hog_start]; int bw_dis = orange[hog_start]; //t时刻俩者间的距离 if (hog_start == n) printf("0\n"); else if (max_dis >= bw_dis) printf("%d\n", max(1, bw_dis)); //表明土拨鼠是在逃跑的路上被捉到的 else printf("%d\n", max(1, (max_dis + bw_dis + 1)/ 2)); //表明土拨鼠是在最远处等着orange来捉 return 0; }