2 条题解
-
5
好不容易啊……终于有一个带代码的题解了……(
能给个顶吗)UPD 8.9 11.44 修改了一下错误的格式,写上了代码用时,修复若干小问题。
分析: 每个点都有一个高度,而要我们求符合要求的路线中,高度值最高与最低的值的差最小。一般求最大-最小的题都可以用二分差值。于是马上得出一个复杂度略(很)高的解法:
- 二分最大-最小
- 枚举最小,算出最大
- dfs 验证算出的范围是否能完成任务(将范围外的点删去)
估算时间复杂度:
(log 1e6) 二分
1e6 枚举下界
5050 dfs
优化一: 海拔值只有2500种,意味着我们只需要枚举下界2500次,即离散化。有多种方式,但为了简单并且方便,可以用STL的set/sort。
优化二: 由于房子你必须经过,所以枚举下界和上界时下界小于等于房子的最小值,上界大于等于房子的最大值。(最强力的剪枝,直接快了1s左右)
优化三: 其实这个有点卡数据,dfs使用时枚举方向的数组顺序要找好,不同顺序用时不同。
优化四: dfs时判断点能不能走,用vis标记,在函数外预处理,可以搞进300ms。
配合代码:
#include <bits/stdc++.h> using namespace std; int n, sx, sy; char s[55][55]; int h[55][55], vis[55][55], tim, sb[2505]; int tx[2505], ty[2505], cnt; int dir[8][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}}; int ans = 0x3f3f3f3f; void dfs(int x, int y, int l, int r) // dfs { if (vis[x][y] == tim || h[x][y] < l || h[x][y] > r) return; // 剪枝 vis[x][y] = tim; for (int i = 0, u, v; i < 8; i++) // 枚举八个方向 if ((u = dir[i][0] + x) >= 0 && u<=n && (v = dir[i][1] + y) >= 0 && v <= n) // 符合条件 dfs(u, v, l, r); // dfs } bool chk(int d, int u) // check { tim++; dfs(sx, sy, d, u); // dfs for (int i = 0; i < cnt; i++) if (vis[tx[i]][ty[i]] != tim) return false; return true; // 只有所有的 vis[tx[i]][ty[i]] == tim 时才返回 true } int main() { // 输入 scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s", s[i]); for(int j = 0; j < n; j++) if (s[i][j] == 'P') sx = i, sy = j; // 设置出发点 else if (s[i][j] == 'K') tx[cnt] = i, ty[cnt++] = j; // 设置目标点 } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &h[i][j]), sb[++sb[0]] = h[i][j]; // 输入高度 sort(sb + 1, sb + sb[0] + 1); // 排序 sb[0] = unique(sb + 1, sb + sb[0] + 1) - sb - 1; // 去重,修改长度 // 核心 for (int i = 1, j = 0; i <= sb[0]; i++) for (; j + 1 <= sb[0] && chk(sb[j + 1], sb[i]); j++) ans = min(ans, sb[i] - sb[j + 1]); printf("%d\n", ans); return 0; } // 终于结束了
AC版:(
这才是最想要的)#include <bits/stdc++.h> using namespace std; int n, sx, sy; char s[55][55]; int h[55][55], vis[55][55], tim, sb[2505]; int tx[2505], ty[2505], cnt; int dir[8][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}}; int ans = 0x3f3f3f3f; void dfs(int x, int y, int l, int r) { if (vis[x][y] == tim || h[x][y] < l || h[x][y] > r) return; vis[x][y] = tim; for (int i = 0, u, v; i < 8; i++) if ((u = dir[i][0] + x) >= 0 && u<=n && (v = dir[i][1] + y) >= 0 && v <= n) dfs(u, v, l, r); } bool chk(int d, int u) { tim++; dfs(sx, sy, d, u); for (int i = 0; i < cnt; i++) if (vis[tx[i]][ty[i]] != tim) return false; return true; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s", s[i]); for(int j = 0; j < n; j++) if (s[i][j] == 'P') sx = i, sy = j; else if (s[i][j] == 'K') tx[cnt] = i, ty[cnt++] = j; } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &h[i][j]), sb[++sb[0]] = h[i][j]; sort(sb + 1, sb + sb[0] + 1); sb[0] = unique(sb + 1, sb + sb[0] + 1) - sb - 1; for (int i = 1, j = 0; i <= sb[0]; i++) for (; j + 1 <= sb[0] && chk(sb[j + 1], sb[i]); j++) ans = min(ans, sb[i] - sb[j + 1]); printf("%d\n", ans); return 0; }
最大用时:500ms
总用时:2.2s
- 1
信息
- ID
- 1989
- 时间
- 4000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- (无)
- 递交数
- 42
- 已通过
- 28
- 上传者