在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。
1<=L<=10^9,
1<=S<=T<=10,
1<=M<=100
输入描述:
第一行有一个正整数L ,表示独木桥的长度。
第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。
所有相邻的整数之间用一个空格隔开。
输出描述:
只包括一个整数,表示青蛙过河最少需要踩到的石子数。
示例1
输入
10
2 3 5
2 3 5 6 7
输出
2
https://www.nowcoder.com/questionTerminal/35ddfeb4e34f410bb9035682463a382f?answerType=1&f=discussion
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
int n = in.nextInt();
int s = in.nextInt();
int t = in.nextInt();
int m = in.nextInt();
ArrayList<Integer> stones = new ArrayList();
for(int i=0;i<m;i++) {
stones.add(in.nextInt());
}
Collections.sort(stones);
if(s==t) {
singleJudge(s,stones);
} else {
rangeJudge(s,t,n,stones);
}
}
}
public static void singleJudge(int s,ArrayList<Integer> stones) {
int stoneNumber = 0;
for(int i=0;i<stones.size();i++) {
if(stones.get(i)%s == 0) {
stoneNumber++;
}
}
System.out.println(stoneNumber);
}
public static void rangeJudge(int s,int t,int n,ArrayList<Integer> stones) {
int compressLen = compressBridgeLength(stones,n,t);
int[] dp = new int[compressLen+t+1];
Arrays.fill(dp,10000);
dp[0] = 0;
int stoneNumber = 10000;
int maxStep = 0;
for(int i=s;i<=compressLen+t;i++) {
maxStep = Math.max(maxStep,i);
for(int j=s;j<=t;j++) {
if(i>=j) {
dp[i] = Math.min(dp[i],dp[i-j]);
}
}
if(stones.contains(i)) {
dp[i] +=1;
}
}
for(int i=compressLen;i<=maxStep;i++) {
stoneNumber = Math.min(dp[i],stoneNumber);
}
System.out.println(stoneNumber);
}
public static int compressBridgeLength(ArrayList<Integer> stones,int n,int t) {
for(int i=1;i<stones.size();i++) {
int distance = stones.get(i) - stones.get(i-1);
stones.set(i,stones.get(i-1) + distance%90);
}
n = (n - stones.get(stones.size()-1))%90 + stones.get(stones.size()-1);
return n;
}
}
给你加了些注释
题解
先不考虑开不下数组的问题
如果我们用f[i]表示走到i这个位置的最小的踩石子的次数话
i这个位置没有石头:f[i]=min(f[i],f[k])
i这个位置是石头:f[i]=min(f[i],f[k]+1)
(k是上一步的位置, [公式] )
现在我们来解决桥太长了数组开不了的问题,我首先仔细看数据范围,相对于桥长度L,石头个数和青蛙跳跃范围S,T都是很小的,也就是说总是存在一些石头离得非常远,从前一个石头到这个石头需要跳很多步才能到达,而只要S和T不等,那么在这漫长的跳跃中我们总可以调整步幅使得踩不到这颗石子。换句话说,只要S和T不等当两个石子之间的距离超过了一定范围之后,任意距离都是可以到达的,这个时候两个离得很远的石头之间的距离就不重要了,那么现在我们就来考虑这个距离是多少:
(其实如果是比赛的时候,你其实可以根据时空限制直接估算这个值,能卡着时空过就行了)
我们先看例子,当S=3,T=4的时候那些长度是可以到达的:
3 、4、 6=3+3、 7=3+4、 8=4+4、 9=3+3+3、 10=3+3+4、 11=3+4+4、 12=4+4+4/3+3+3+3、13、14、15……
S=5,T=6时:
5、6、10=5+5、11=5+6、12=6+6、15=5+5+5、16=5+5+6、17=5+6+6、18=6+6+6、20=5+5+5+5、21=5+5+5+6、22=5+5+6+6、23=5+6+6+6、24=6+6+6+6、25=5+5+5+5+5、26=5+5+5+5+6、27=5+5+5+6+6、28=5+5+6+6+6、29=5+6+6+6+6、30=6+6+6+6+6/5+5+5+5+5+5……
我们发现,当长度超过 [公式] 之后,这个长度会有至少两种跳的方式(T个S相加和S个T相加),之后我们可以在每一步比都在较小的那种方法(T个S相加)的基础上将某些步的长度变大,然后就可以跳出更长的长度,也就是说 [公式] 及其之前的所有长度都可以跳出来,然后 [公式] 自然也有它自己的表达方式,之后的长度也都可以在S的整数倍的基础上调整得来。
对于本题来说,最大的 [公式] 的取值是 [公式] ,也就是说我们让任意两个距离大于90的石头距离为90就可以了,这样时间空间都满足了!
(S==T的情况直接特判)
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
int n = in.nextInt();//表示独木桥的长度。
int s = in.nextInt();//表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数
int t = in.nextInt();//表示青蛙一次跳跃的最大距离
int m = in.nextInt();//桥上石子的个数
ArrayList<Integer> stones = new ArrayList();
for(int i=0;i<m;i++) {//第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。
//所有相邻的整数之间用一个空格隔开。
stones.add(in.nextInt());
}
Collections.sort(stones);//对M个石子进行排序,从小到大
if(s==t) {
singleJudge(s,stones);//输出青蛙过河最少需要踩到的石子数
} else {
rangeJudge(s,t,n,stones);//s!=t时候执行
}
}
}
public static void singleJudge(int s,ArrayList<Integer> stones) {
int stoneNumber = 0;
for(int i=0;i<stones.size();i++) {
if(stones.get(i)%s == 0) {
stoneNumber++;
}
}
System.out.println(stoneNumber);//表示青蛙过河最少需要踩到的石子数
}
public static void rangeJudge(int s,int t,int n,ArrayList<Integer> stones) {
int compressLen = compressBridgeLength(stones,n,t);
int[] dp = new int[compressLen+t+1];//定义数组长度为compressLen+t+1
Arrays.fill(dp,10000);//给数组填充10000数据
dp[0] = 0;//数组第一元素初始化0
int stoneNumber = 10000;//石头数量
int maxStep = 0;//最大步数
for(int i=s;i<=compressLen+t;i++) {
maxStep = Math.max(maxStep,i);//求最大步数
for(int j=s;j<=t;j++) {//递归找到最小的
if(i>=j) {
dp[i] = Math.min(dp[i],dp[i-j]);//求dp[i],dp[i-j]中小的
}
}
if(stones.contains(i)) {//石头中包含i
dp[i] +=1;//加1
}
}
for(int i=compressLen;i<=maxStep;i++) {//递归范围从maxStep,找到最小的石头
stoneNumber = Math.min(dp[i],stoneNumber);//求dp[i],stoneNumbe中小的
}
System.out.println(stoneNumber);
}
public static int compressBridgeLength(ArrayList<Integer> stones,int n,int t) {
for(int i=1;i<stones.size();i++) {
int distance = stones.get(i) - stones.get(i-1);//求石头i和i-1距离
stones.set(i,stones.get(i-1) + distance%90);//求石头i赋值第i-1个石头距离加上 石头i和i-1距离除以90余数
}
n = (n - stones.get(stones.size()-1))%90 + stones.get(stones.size()-1);
return n;
}
}
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;
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()));
}
}
把代码一行一行理解,
自己尝试去修改一些数值,
然后反复运行,
这样可以帮助自己理解每一行代码的意思