首页 > itarticle > poj 3278 catch that cow

poj 3278 catch that cow

admin 11月 13, 2020 0

http://poj.org/problem?id=3278
Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

  • Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
  • Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K
Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

设d[ ][0/1/2] 分别为正向，跳跃，逆向行走时的最小值
N 是 可以小于 K 的，此时直接输出 abs( n-i ) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 

#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#include <utility>
#include <vector>
#include <map>
#include <stack> 
#include <climits> 
using namespace std;
typedef long long ll;
#define INF INT_MAX
#define MAX 200000+10 
int d[MAX][3],n,k;
int (){
	freopen("file/in","r",stdin);
	
	while(~scanf("%d %d",&n,&k)){
		if(n>k) {
			printf("%dn",abs(n-k));
			continue;
		}
		for(int i=n;i<=2*k;i++){
			d[i][0]=MAX;
			d[i][1]=MAX;
			d[i][2]=MAX;
		}
		d[n][0]=0;d[n][1]=0;
		d[n][2]=0;d[2*n][1]=1;
		for(int i=n-1;i>n/2;i--){
			d[i][2]=d[i+1][2]+1;
			d[i*2][1]=d[i][2]+1;
		}
		for(int i=n+1;i<=k;i++){
			d[i][0]=min(d[i-1][0],d[i-1][1])+1;
			d[i][2]=min(d[i+1][2],d[i+1][1])+1;
			d[i*2][1]=min(min(d[i][0],d[i][2]),d[i][1])+1;
		}
		printf("%dn",min(d[k][0],min(d[k][1],d[k][2])));
	}
	return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能