The Lost cow[USACO-2017-USOpen-B]

### 解题思路 "The Lost Cow" 是一道经典的模拟问题，目标是计算 Farmer John 找到 Bessie 需要行走的距离。Farmer John 使用一种特定的策略来寻找 Bessie：他从初始位置 `x` 开始，依次向右走一段距离，再返回原点；接着向左走更远的一段距离，再次回到原点，如此反复直到找到 Bessie。 #### 关键逻辑 1. **移动模式** 每次移动的距离按照序列 \( \pm 1, \mp 2, \pm 4, \ldots \) 增加，即每次翻倍并改变方向。 2. **终止条件** 当 Farmer John 到达的位置覆盖了 Bessie 的实际坐标 `y` 时停止搜索。具体来说： - 如果 `x < y`，则当某一次移动到达或超过 `y` 时结束； - 如果 `x > y`，则当某一次移动到达或低于 `y` 时结束。 3. **总路径长度** 计算总的路径长度时需要注意最后一次未完全完成的往返行程应减去多余的部分。 --- ### C++ 实现代码 以下是基于上述逻辑的一个标准实现： ```cpp #include <iostream> #include <cmath> using namespace std; int main() { long long x, y; cin >> x >> y; if (x == y) { cout << 0; return 0; } long long pos = x, step = 1, total_distance = 0; while (true) { // 向右移动 long long next_pos = pos + step; if ((x < y && next_pos >= y) || (x > y && next_pos <= y)) { total_distance += abs(y - pos); break; } total_distance += abs(next_pos - pos); pos = next_pos; // 返回起点 total_distance += abs(pos - x); // 向左移动 step *= -2; next_pos = pos + step; if ((x < y && next_pos >= y) || (x > y && next_pos <= y)) { total_distance += abs(y - pos); break; } total_distance += abs(next_pos - pos); pos = next_pos; // 返回起点 total_distance += abs(pos - x); step *= -2; } cout << total_distance; return 0; } ``` 此代码实现了 Farmer John 寻找 Bessie 的过程，并精确计算了所需的总路径长度[^1]。 --- ### Pascal 实现代码 如果偏好 Pascal，则可以参考以下代码片段： ```pascal var n, x, y, t, ans: longint; begin assign(input, 'lostcow.in'); reset(input); assign(output, 'lostcow.out'); rewrite(output); readln(x, y); if x = y then begin writeln(0); halt; end; n := x; t := 1; ans := 0; repeat ans := ans + abs(t) + abs(n - x); n := x + t; t := -t * 2; if ((n >= y) and (x < y)) or ((n <= y) and (x > y)) then begin ans := ans - abs(n - y); break; end; until false; writeln(ans); close(input); close(output); end. ``` 这段代码同样遵循相同的逻辑结构，适用于需要提交至 USACO 平台的情况[^3]。 --- ### Python 实现代码 对于初学者而言，Python 提供了一种更为简洁的方式表达这一算法： ```python def lost_cow(x, y): if x == y: return 0 position = x step = 1 total_distance = 0 while True: # Move to the right new_position = position + step if (x < y and new_position >= y) or (x > y and new_position <= y): total_distance += abs(new_position - position) total_distance -= abs(new_position - y) break total_distance += abs(new_position - position) position = new_position total_distance += abs(position - x) # Move to the left step *= -2 new_position = position + step if (x < y and new_position >= y) or (x > y and new_position <= y): total_distance += abs(new_position - position) total_distance -= abs(new_position - y) break total_distance += abs(new_position - position) position = new_position total_distance += abs(position - x) return total_distance # Example usage print(lost_cow(int(input()), int(input()))) ``` 该版本通过逐步调整步长和方向完成了整个搜索流程[^4]。 ---