[ABC257D] Jumping Takahashi 2
博客食用更佳:My blog。
大体思路
这题是一道二分题,因为 \(S\) 越大,就越容易满足题目要求,\(S\) 越小,就越难满足题目要求,符合二分的特点。
下面先贴上二分代码。
LL l = 0, r = 1e10;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r;// 二分板子。
check 函数怎么写
因为这题 \(n\) 比较小,所以我们可以在每次 check 时,枚举起点,每次从那个点深搜一遍,然后判断搜索到的点数量是否为 \(n\),若搜到了 \(n\) 个点,直接返回 \(1\),若所有点都没有搜到 \(n\) 个点,返回 \(0\)。
下面是 check 函数代码。
bool check(LL mid) {
for (LL i = 1; i <= n; i++) {
memset(vis, 0, sizeof vis);// vis 用来标记是否已访问过。
cnt = 0;// 用来记录访问了几个点,cnt 和 vis 数组每次都要清空。
dfs(i, mid);// 搜索。
if (cnt == n) return 1;
}
return 0;
}
dfs 函数怎么写
dfs 传参要传两个参数:当前点和训练次数。每次判断每个点是否之前被访问过,访问过就结束掉,没访问过就把这个点标记为 \(1\),接着枚举下一个点,继续搜索。
下面就是代码。
void dfs(LL u, LL mid) {
if (vis[u]) return; // 查看是否访问过。
vis[u] = 1, cnt++;
for (LL v = 1; v <= n; v++) { // 枚举每个点。
if (p[u] * mid < abs(x[u] - x[v]) + abs(y[u] - y[v])) continue; // 到不了就 continue。
dfs(v, mid);
}
}
Code
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL N = 205;
LL n, x[N], y[N], p[N], cnt, vis[N];
void dfs(LL u, LL mid) {
if (vis[u]) return;
vis[u] = 1, cnt++;
for (LL v = 1; v <= n; v++) {
if (p[u] * mid < abs(x[u] - x[v]) + abs(y[u] - y[v])) continue;
dfs(v, mid);
}
}
bool check(LL mid) {
for (LL i = 1; i <= n; i++) {
memset(vis, 0, sizeof vis);
cnt = 0;
dfs(i, mid);
if (cnt == n) return 1;
}
return 0;
}
signed main() {
cin >> n;
for (LL i = 1; i <= n; i++) cin >> x[i] >> y[i] >> p[i];
LL l = 0, r = 1e10;
while (l < r) {
LL mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r;
return 0;
}
谨记
一定要开 long long。
题解结束了,有问题大家可以私信我。
标签:题解,LL,mid,long,vis,Jumping,dfs,abc257,check From: https://www.cnblogs.com/0x3f3f3f3f3f3f/p/18391215