做题时不知道哪里出错了,对照答案仍不知道,求解

描述
在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。
对于30%的数据,L <= 10000;
对于全部的数据,L <= 10^9。
格式
输入格式

输入的第一行有一个正整数L(1 <= L <= 10^9),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。
输出格式

输出只包括一个整数,表示青蛙过河最少需要踩到的石子数。
样例1
样例输入1
10
2 3 5
2 3 5 6 7
样例输出1
2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {

// 用于储存某点的最少石头数,每次搜索时访问,若无记录添加并继续,若有记录比较,较多或相等则退出,较少则更新并继续
// key=long 位置
// value=int 最少踩到的石头数
static HashMap<Long, Integer> stoneL = new HashMap<Long, Integer>();

// 用于储存石头的位置 用 containsKey(key)搜索
static HashMap<Long, Integer> stoneP = new HashMap<Long, Integer>();

// 桥长long L
static long l;

// 跳跃距离介于int S T
static int s, t;

// 石子个数int M
static int m;

// 用于实现广度搜索的栈 long 位置 int 石头数
static TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();

static TreeSet<Long> ts=new TreeSet<Long>();



// 递归广度搜索函数
static void jump(long formPoint, int formStone) {


    for (int i = s; i < t + 1&&formPoint<l; i++) {
        long curPoint = formPoint + i;
        int curStone = formStone;
        // 如果该点有石头,当前踩到石头数+1
        if (stoneP.containsKey(curPoint)) {
            curStone += 1;
        }
        // 如果表中无该点数据,添加
        if (!stoneL.containsKey(curPoint)) {
            stoneL.put(curPoint, curStone);
            tm.put(curPoint, curStone);
            // 如果有数据,进行比较
            // 如果少于一直最少石头,更新
        } else if (curStone < stoneL.get(curPoint)) {
            stoneL.put(curPoint, curStone);
            tm.put(curPoint, curStone);
            // 如果多于已知最少石头,跳过
        } else {
            continue;
        }
    }

    while(!tm.isEmpty()){
        long pointStack=tm.firstKey();
        int stoneStack=tm.get(pointStack);
        tm.remove(pointStack);

        jump(pointStack,stoneStack);
    }
}

public static void main(String[] args) throws Exception {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    l = Long.valueOf(br.readLine());
    l=0;//此处清空了l
    String str = br.readLine();
    String[] sstr = str.split(" ");
    s = Integer.valueOf(sstr[0]);
    t = Integer.valueOf(sstr[1]);
    m = Integer.valueOf(sstr[2]);
    str = br.readLine();
    sstr = str.split(" ");

    for (String ss : sstr) {
        ts.add(Long.valueOf(ss));
    }

    if(s==t){
        int count=0;
        for (Long sto : ts) {
            if(sto%s==0){
                count++;
            }
        }
        System.out.println(count);
        return;
    }


    long yusto=0;
    for (Long sto : ts) {
        if(sto-yusto>81){
            l+=81;
        }else{
            l=l+sto-yusto;
        }
        stoneP.put(l, 1);
        yusto=sto;
    }

    jump(0,0);

    TreeMap<Long, Integer> tm2 = new TreeMap<Long, Integer>();

    for(long j=l;j<l+t;j++){
        if(stoneL.containsKey(j)){
            tm2.put(j, stoneL.get(j));
            }
    }

    System.out.println(tm2.get(tm2.firstKey()));
    // 输出
}

}

0

1个回答

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题

10
newFixedThreadPool例子无法运行求解
4
杭电Java2023 我自己的测试数据跟AC过的代码是一样的输出,不明白错在哪里,求大神指教
11
SSM整合,测试时提示NoSuchBeanDefinitionException
13
JAVA int是-2147483648时,Math.abs()无法将其转成正数,为什么?
3
java socket编程,发送了一个18kb大小的数据时发现发不了,请问如何解决
5
Collections.sort报错,大神求分析、求答案
1
java读取邮件时过滤广告,垃圾邮件。
3
疑似jsp页面过长导致编译错误请求,用include 也不好搞,求解思路。
4
java读取文件时,判断文件类型与后缀是否一致
3
Javaweb项目中需要一个计时器,刷新或退出该页面时,计时器仍在跑
4
我在java项目中加了jar包,不知道为什么还是报错
11
使用maven运行jsp时跳转出错
3
急。。。有一个多用户的Javaweb系统,如何采集每个用户使用该系统时所消耗的网络流量啊?
3
java httpclient请求时 用EntityUtils解析时出现问题
2
用php写出下面java的代码,不知道php有没有对字节的压缩?
8
javamail 收邮件时正文+图片时为什么图片没有显示,这个是怎么解析img里src下的cid
2
javamail 收邮件时正文+图片时为什么图片没有显示,这个是怎么解析img里src下的cid
10
用IDEA导入maven工程后发现java文件像僵尸一样不提示也不报错了,各位高高手请指点一下江山
9
java 求大神看看哪里错了
4
java 求大神看看哪里出错了,代码想这样实现:运用两个按钮分别打开两个新界面,并实现自己的功能