一只袋鼠要从河这边跳到河对岸, 河很宽, 但是河中间打了很多桩子, 每隔一米就有一个, 每个桩子上都有一个弹簧, 袋鼠跳到弹簧上就可以跳的更远. 每个弹簧力量不同, 用一个数字代表它的力量, 如果弹簧力量为5, 就代表袋鼠下一跳最多能够跳5米, 如果为0, 就会陷进去无法继续跳跃. 河流一共N米宽, 袋鼠初始位置就在第一个弹簧上面, 要跳到最后一个弹簧之后就算过河了, 给定每个弹簧的力量, 求袋鼠最少需要多少跳能够到达对岸. 如果无法到达输出-1
输入描述:
输入分两行, 第一行是数组长度N (1 ≤ N ≤ 10000), 第二行是每一项的值, 用空格分隔.输出描述:
输出最少的跳数, 无法到达输出-1示例1
输入
5
2 0 1 1 1输出
4
这是一题在牛客网上的编程练习题, 最暴力的方法就是从袋鼠跳的过程拓展成一棵树, 但是由于N比较大, 这样有可能这棵树就比较庞大, 通过广度优先所搜索来确定最短路径的时间复杂度就较大, 不是很现实.
动态规化来求解
如果我们用 F(n) 来表示到达 第 n 个桩所需要的最少步数, 那么我们可以根据第 n 个桩可以跳的距离 d 来更新 F(n+1), F(n+2) .. F(n+d), 记作 F(n+k) = min(F(n+k), F(n)+1), k=1..d, F(n) 初始值为 INT_MAX, 其中, F(0)=F(1)0, F(n+1)也就是目的地为-1.
如果袋鼠到达不了对岸, 那么F(n+1)要么是-1要么是 INT_MAX+1 也就是会溢出成为负数, 这时候输出-1, 否则答案就是 F(n+1).
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 | #include <iostream> #include <vector> #include <climits> using namespace std; int main() { int n; cin >> n; vector<int> arr(n + 2, n + 1); //桩子 vector<int> ans(n + 2, INT_MAX); // 到达每个桩子的最少步数 ans[n + 1] = -1; ans[0] = 0; ans[1] = 0; for (int i = 1; i <= n; ++ i) { cin >> arr[i]; // 输入 } for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= arr[i] && i + j <= n + 1; ++ j) { if (ans[i + j] == -1) { ans[i + j] = ans[i] + 1; } else { ans[i + j] = min(ans[i + j], ans[i] + 1); } } } cout << (ans[n + 1] < 0 ? -1 : ans[n + 1]) << endl; return 0; } |
#include <iostream> #include <vector> #include <climits> using namespace std; int main() { int n; cin >> n; vector<int> arr(n + 2, n + 1); //桩子 vector<int> ans(n + 2, INT_MAX); // 到达每个桩子的最少步数 ans[n + 1] = -1; ans[0] = 0; ans[1] = 0; for (int i = 1; i <= n; ++ i) { cin >> arr[i]; // 输入 } for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= arr[i] && i + j <= n + 1; ++ j) { if (ans[i + j] == -1) { ans[i + j] = ans[i] + 1; } else { ans[i + j] = min(ans[i + j], ans[i] + 1); } } } cout << (ans[n + 1] < 0 ? -1 : ans[n + 1]) << endl; return 0; }
这题动态规化算法的时间复杂度是 O(N^2), 空间复杂度是 O(N)
贪心算法
有没有更快的方法呢? 我们可以通过贪心算法来简化计算. 我们可以记录袋鼠每次可以跳的最远距离和位置, 然后不停的更新, 如果袋鼠可以跳到当前桩子, 就更新步数和当前最佳. 不过最后的时候需要判断是否能跳到对岸.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> arr(n, 0); for (int i = 0; i < n; ++ i) { cin >> arr[i]; // 输入 } int best = 0, jump = 0, cur = 0; for (int i = 0; i < n; ++ i) { best = max(best, i + arr[i]); // 最远位置 if (cur == i) { // 如果袋鼠可以跳到当前桩子 jump ++; cur = best; } } cout << (cur >= n ? jump : -1); return 0; } |
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> arr(n, 0); for (int i = 0; i < n; ++ i) { cin >> arr[i]; // 输入 } int best = 0, jump = 0, cur = 0; for (int i = 0; i < n; ++ i) { best = max(best, i + arr[i]); // 最远位置 if (cur == i) { // 如果袋鼠可以跳到当前桩子 jump ++; cur = best; } } cout << (cur >= n ? jump : -1); return 0; }
比如: 输入为 1 0 0 0 0 3 0 的时候袋鼠是无法跳到对岸的, 这时候只需要判断 cur 是不是已经大于 n 也就是跳到对岸了. 这个时间复杂度是 O(N), 空间复杂度是 O(1) 如果不考虑输入的话.
loading...
上一篇: 最简单有效的过滤Wordpress垃圾评论的方法
下一篇: Steem 终于升到 72级