欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

2020暑假牛客多校第九场 K The Flee Plan of Groundhog (树形结构/思维)

程序员文章站 2022-03-03 11:43:18
The Flee Plan of Groundhog 题目大意:有一个土拨鼠在节点1,一个橘子在节点n,在t时刻之前土拨鼠向着n走,橘子不动,从t时刻开始,橘子开始抓土拨鼠,土拨鼠开始跑,土拨鼠 1m/s 橘子 2m/s,问还有多长时间橘子才能抓到土拨鼠。解题思路:t 时刻之后,土拨鼠必然朝着n的反方向移动,土拨鼠走一步,橘子走两步,那么我们可以记录一下t时刻土拨鼠的位置,还有土拨鼠向反方向最多能跑多远。如果土拨鼠向后跑了一步就到头了,那么显然时间是橘子到改点的距离/2向上取整,但是如果土拨鼠可以向...

The Flee Plan of Groundhog

题目大意:
有一个土拨鼠在节点1,一个橘子在节点n,在t时刻之前土拨鼠向着n走,橘子不动,从t时刻开始,橘子开始抓土拨鼠,土拨鼠开始跑,土拨鼠 1m/s 橘子 2m/s,问还有多长时间橘子才能抓到土拨鼠。

解题思路:
t 时刻之后,土拨鼠必然朝着n的反方向移动,土拨鼠走一步,橘子走两步,那么我们可以记录一下t时刻土拨鼠的位置,还有土拨鼠向反方向最多能跑多远。如果土拨鼠向后跑了一步就到头了,那么显然答案是橘子到该点的距离/2向上取整,但是如果土拨鼠可以向后跑很多步,在跑的过程中被逮住了,那么答案就是土拨鼠往后跑的距离的时间。

  • 土拨鼠向后跑到了最远处没法再跑蹲躲在角落等着橘子来抓
  • 土拨鼠向后跑的过程中被橘子逮住了

分类讨论一下即可。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500000;

vector<int> ve[maxn];
int dis[maxn],f[maxn],m,ed=1,maxx=0;

void dfs(int x,int pre,int val){  //记录下每个点到n的距离 
	f[x]=pre;
	dis[x]=val;
	for(int i=0;i<ve[x].size();i++){
		if(ve[x][i]==pre) continue;
		dfs(ve[x][i],x,val+1);
	}
}

void dfs2(int x,int pre){
	maxx=max(maxx,dis[x]);      //从t时间所在地点往n点相反的方向跑最远是多少
	for(int i=0;i<ve[x].size();i++){
		if(ve[x][i]==pre) continue;
		dfs2(ve[x][i],x);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

    int t,n,tmp=1;
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    dfs(n,n,0);
	while(m--) tmp=f[tmp];  //找出土拨鼠的t时间所在的节点 
	dfs2(tmp,f[tmp]);

	int x=maxx-dis[tmp];      
	int y=dis[tmp];          // 拨鼠的t时间所在的节点到n的距离 

	if(tmp==n) cout<<"0\n";        //土拨鼠在t时间之前到了n点 
	else if(x-y>=0) cout<<max(1,y)<<endl; //土拨鼠跑到最远点之前被橘子逮住了 
	else cout<<max(1,(maxx+1)/2)<<endl;  // 土拨鼠跑到最远点了然后没法再跑了,躲在角落等着橘子来抓 
	
	
	return 0;
}

本文地址:https://blog.csdn.net/weixin_43872264/article/details/107884908

相关标签: 图论 dfs