USACO算法题snowboots代码修复求助：靴子切换约束问题

Hey there! 作为算法竞赛的新手，你能写出这样的贪心框架已经很棒了——咱们来一步步把这个约束问题搞定，你的代码完全有挽救的空间😉

问题核心分析 #

你之前忽略的关键规则是：Farmer John只能在「当前靴子能站立」且「新靴子也能站立」的瓷砖上切换靴子。原代码的问题在于，当当前靴子跳不动时直接切换到下一双，完全没检查当前位置是否符合新靴子的站立条件，这就导致了非法切换的情况。

基于原代码的最小修改方案 #

我们不需要完全推翻原有逻辑，只需要添加「切换前的合法性检查」和「往回找合法切换位置」的逻辑即可，原代码的贪心跳跃逻辑可以完整保留。

修改点说明

1. 新增moveBack方法：支持往回跳，帮助我们找到当前靴子能到达的、同时符合新靴子站立条件的位置。
2. 优化solve方法的切换逻辑：
   • 先用当前靴子跳到最远位置
   • 检查当前位置是否能直接切换到下一双靴子
   • 如果不能，先在当前靴子的回跳范围内找合法位置；找不到就循环往回跳，直到找到符合条件的位置再切换

完整修改后的代码

import java.io.*;
import java.util.*;
public class snowboots {
static int n,k;
static int[] field,a,b; //a,b --> strength, distance
static int pos;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("snowboots.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("snowboots.out")));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
field = new int[n];
a = new int[k];
b = new int[k];
for (int i = 0; i < n; i++)
field[i] = Integer.parseInt(st.nextToken());
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
a[i] = Integer.parseInt(st.nextToken());
b[i] = Integer.parseInt(st.nextToken());
}
pw.println(solve());
pw.close();
}
static int solve() {
    pos = 0;
    int i = 0;
    while(pos < n-1) {
        // 用当前靴子尽可能往前跳
        while(move(i));
        
        // 到达终点直接退出
        if (pos >= n-1) break;
        
        // 已经是最后一双靴子，无需切换（题目保证有解）
        if (i >= k-1) break;
        
        // 检查当前位置是否能直接切换到下一双靴子
        if (field[pos] <= a[i+1]) {
            i++;
            continue;
        }
        
        // 往回找合法的切换位置
        boolean found = false;
        // 先在当前靴子能跳回的范围内查找
        int start = Math.max(0, pos - b[i]);
        for (int x = pos - 1; x >= start; x--) {
            if (field[x] <= a[i] && field[x] <= a[i+1]) {
                pos = x;
                found = true;
                break;
            }
        }
        
        // 范围内没找到，继续往回跳查找
        if (!found) {
            while (moveBack(i)) {
                if (field[pos] <= a[i+1]) {
                    found = true;
                    break;
                }
            }
        }
        
        // 切换到下一双靴子
        i++;
    }
    return i;
}
static boolean move(int c) {
    // 往前跳，优先选择最远的可行位置
    for (int i = pos+b[c]; i > pos; i--) {
        if (i < n && field[i] <= a[c]) {
            pos = i;
            return true;
        }
    }
    return false;
}

static boolean moveBack(int c) {
    // 往回跳，优先选择离当前位置最近的可行位置
    int start = Math.max(0, pos - b[c]);
    for (int i = pos - 1; i >= start; i--) {
        if (field[i] <= a[c]) {
            pos = i;
            return true;
        }
    }
    return false;
}
}

为什么这样修改有效？ #

• 保留了你原有的贪心跳跃逻辑（每次跳最远），保证了效率
• 切换靴子前严格检查位置合法性，确保只有在新旧靴子都能站立的瓷砖上才会切换
• 当当前位置不合法时，通过往回跳找到最近的合法位置，避免了过度限制导致的无法前进问题

内容的提问来源于stack exchange，提问作者HackerMan