#P1575. 2023.04.26-暑期实习-第三题-MC方块
-
ID: 16
Tried: 24
Accepted: 5
Difficulty: 6
2023.04.26-暑期实习-第三题-MC方块
题目内容
MC最新版本更新了一种特殊的方块,幽匿催发体。这种方块能够吸收生物死亡掉落的经验并感染周围方块,使其变成幽匿块。Steve想要以此为基础尝试搭建一个经验仓库,他来到了创造超平坦模式,在只有草方块组成的平坦世界上进行他的实验。
在Steve的实验中,幽匿催发体可以看做每次吸收经验后会向自己平面方向上的周围八个方块进行感染,使其变成幽匿催发体。Steve任意选择了 n 个坐标点作为幽匿催发体的起始方块,接下来每天都会给予这些催发体足够使自身范围向外扩展一圈的经验。当有两个或以上的幽匿催发体的感染范围重叠时,重叠区域的方块会吸收更多的经验,吸收经验的数量为该方块所在不同幽匿催发体感染范围数量的整数倍。
如下方三张图所示,蓝色点A、B为初始幽匿催发体的位置
第二天,向周围扩散感染
第三天,两个催发体的感染范围出现重叠,重叠部分的经验倍数 M 为2,其余则为1,以此类推。
Steve想要知道多少天以后,会出现至少有一个方块的经验存储量的倍数可以达到给定的 M ?
输入描述
第一行输入整数 M。(2c= M <= n)
第二行输入幽匿催发体个数 n。 (2<= n <= 50)
后面连续 n 行输入第 i 个幽匿催发体 i 的初始位置 [xi, yi]。 (1<= xi,yi<= 10^9)
输出描述
输出找到一个方块至少同时处在 M 个幽匿催发体的感染范围的最少天数,找不到返回 0
样例
样例1
输入
2
2
2 1
6 2
输出
2
说明
说明: 在第2天,点(4.0)、(4.1)、 (4.2)与(4,3)将同时处在两个幽匿催发体发感染范围,如图红色点所示。
样例2
输入
2
3
2 1
6 2
100 100
输出
2
题目大意
在Minecraft的最新版本中,增加了一种特殊的方块——幽匿催发体。该方块能够吸收生物死亡掉落的经验,并感染周围的方块。Steve决定利用这种方块建立一个经验仓库。幽匿催发体每天会扩展其感染范围,吸收周围方块的经验。如果两个或多个幽匿催发体的感染范围重叠,重叠区域的方块将吸收更多的经验。Steve希望知道多少天后,会有至少一个方块的经验存储量达到给定的倍数M。
思路:二分答案+二维差分
1.二分答案:
该问题的答案是关于天数的,随着天数的增加,幽匿催发体的感染范围会增加,重叠的区域也会增加。因此,天数与结果之间存在单调性,即天数越久,达到条件的可能性越大。
2.检查函数:
由于平面太大,无法直接模拟,所以使用二维差分数组来表示幽匿催发体的感染范围。通过离散化处理关键点,降低计算复杂度。
思路步骤
1.输入处理:
读取幽匿催发体的数量和每个幽匿催发体的初始坐标。
2.差分数组构建:
对每个幽匿催发体的位置,更新差分数组,标记感染的区域。
3.离散化:
将每个幽匿催发体的感染范围的坐标进行离散化,方便在一个小范围内进行计算。
4.前缀和计算:
在差分数组上进行前缀和操作,以获得每个点被多少个幽匿催发体感染的数量。
5.计算结果:
根据前缀和的结果计算出重叠区域的数量,判断是否达到给定的 M 倍数。
6.二分查找:
通过二分查找的方法确定达到条件所需的最小天数。
7.输出结果:
输出最终计算的结果,若无法达到,则返回 0。
代码说明
代码
C++
#include<bits/stdc++.h>
using namespace std;
const int N = 55; // 定义最大幽匿催发体数量
typedef pair<int, int> PII; // 定义坐标对的类型
#define x first
#define y second
vector<PII> w; // 存储幽匿催发体的坐标
int n, m; // n 为幽匿催发体数量,m 为目标倍数
// 检查给定天数 mid 是否能达到目标 M
int check(vector<PII>& ps, int mid) {
// 1. 统计所有左下和右上坐标
vector<long long> xs, ys; // 存储坐标的向量
for (auto &p : ps) {
auto i = p.x; // 获取幽匿催发体的 x 坐标
auto j = p.y; // 获取幽匿催发体的 y 坐标
xs.push_back(i - mid); // 左下角
xs.push_back(i + mid); // 右上角
ys.push_back(j - mid); // 左下角
ys.push_back(j + mid); // 右上角
}
// 2. 排序去重
sort(xs.begin(), xs.end()); // 对 x 坐标排序
xs.erase(unique(xs.begin(), xs.end()), xs.end()); // 去重
sort(ys.begin(), ys.end()); // 对 y 坐标排序
ys.erase(unique(ys.begin(), ys.end()), ys.end()); // 去重
// 3. 二维差分
int n = xs.size(), m = ys.size(); // 获取去重后的坐标数量
int diff[n + 2][m + 2]; // 初始化差分数组
memset(diff, 0, sizeof(diff)); // 将差分数组初始化为 0
for (auto &p : ps) {
auto i = p.x; // 获取幽匿催发体的 x 坐标
auto j = p.y; // 获取幽匿催发体的 y 坐标
// 找到影响区域的边界
int r1 = lower_bound(xs.begin(), xs.end(), i - mid) - xs.begin(); // 左边界
int r2 = lower_bound(xs.begin(), xs.end(), i + mid) - xs.begin(); // 右边界
int c1 = lower_bound(ys.begin(), ys.end(), j - mid) - ys.begin(); // 下边界
int c2 = lower_bound(ys.begin(), ys.end(), j + mid) - ys.begin(); // 上边界
// 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 1
// 多 +1 是为了方便求后面复原
++diff[r1 + 1][c1 + 1]; // 增加影响
--diff[r1 + 1][c2 + 2]; // 减少影响
--diff[r2 + 2][c1 + 1]; // 减少影响
++diff[r2 + 2][c2 + 2]; // 恢复影响
}
// 4. 直接在 diff 上复原,计算最大值
int ans = 0; // 初始化最大重叠数量
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
// 计算当前点的实际重叠数量
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
ans = max(ans, diff[i][j]); // 更新最大值
}
}
return ans; // 返回最大重叠数量
}
int main() {
cin >> m >> n; // 读取目标 M 和幽匿催发体数量
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y; // 读取每个幽匿催发体的坐标
w.push_back({x, y}); // 存储坐标
}
int l = 0, r = 1e9; // 二分查找的边界
while (l < r) {
int mid = (l + r) >> 1; // 计算中间值
if (check(w, mid) >= m) { // 检查是否能达到目标 M
r = mid; // 更新右边界
} else {
l = mid + 1; // 更新左边界
}
}
cout << l << endl; // 输出结果
return 0; // 程序结束
}
python
M = int(input()) # 读取目标倍数 M
n = int(input()) # 读取幽匿催发体的数量 n
c = [] # 存储幽匿催发体的坐标
for i in range(n):
x, y = map(int, input().split()) # 读取每个幽匿催发体的坐标
c.append((x, y)) # 将坐标添加到列表中
def check(day):
xs = set() # 用于存储 x 坐标的集合
ys = set() # 用于存储 y 坐标的集合
# 1. 统计所有左下和右上坐标
for x, y in c:
xs.add(x - day) # 计算幽匿催发体左下角的 x 坐标
xs.add(x + day) # 计算幽匿催发体右上角的 x 坐标
ys.add(y - day) # 计算幽匿催发体左下角的 y 坐标
ys.add(y + day) # 计算幽匿催发体右上角的 y 坐标
# 2. 排序去重
xs = sorted(xs) # 对 x 坐标排序
ys = sorted(ys) # 对 y 坐标排序
xs_idx = {x: i + 1 for i, x in enumerate(xs)} # 为 x 坐标建立索引映射
ys_idx = {x: i + 1 for i, x in enumerate(ys)} # 为 y 坐标建立索引映射
# 二维差分
diff = [[0] * (len(ys) + 2) for _ in range(len(xs) + 2)] # 初始化差分数组
for x, y in c:
# 获取当前幽匿催发体影响的区域
x_idx = xs_idx[x - day] # 获取左下角的 x 坐标索引
x_idx_ = xs_idx[x + day] + 1 # 获取右上角的 x 坐标索引
y_idx = ys_idx[y - day] # 获取左下角的 y 坐标索引
y_idx_ = ys_idx[y + day] + 1 # 获取右上角的 y 坐标索引
# 更新差分数组
diff[x_idx][y_idx] += 1 # 在当前区域增加影响
diff[x_idx_][y_idx] -= 1 # 在右上角区域减少影响
diff[x_idx][y_idx_] -= 1 # 在右下角区域减少影响
diff[x_idx_][y_idx_] += 1 # 在左上角区域恢复影响
ans = 0 # 初始化最大重叠数量
# 4. 直接在 diff 上复原,计算最大值
for i in range(1, len(xs) + 1):
for j in range(1, len(ys) + 1):
# 计算当前点的实际重叠数量
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]
ans = max(ans, diff[i][j]) # 更新最大重叠数量
return ans # 返回最大重叠数量
# 获取幽匿催发体坐标的最大值和最小值
max_x = max(c)[0] # 获取 x 坐标的最大值
min_x = min(c)[0] # 获取 x 坐标的最小值
max_y = max(c, key=lambda x: x[1])[1] # 获取 y 坐标的最大值
min_y = min(c, key=lambda x: x[1])[1] # 获取 y 坐标的最小值
l = 0 # 二分查找的左边界
r = max(max_x - min_x, max_y - min_y) // 2 + 2 # 二分查找的右边界
# 二分查找
while l < r:
mid = (l + r) // 2 # 计算中间值
tmp = check(mid) # 检查当前天数的重叠数量
if tmp == M: # 如果当前重叠数量正好等于 M
r = mid # 更新右边界
elif tmp < M: # 如果当前重叠数量小于 M
l = mid + 1 # 更新左边界
else: # 如果当前重叠数量大于 M
r = mid # 更新右边界
print(r) # 输出结果
Java
超时
import java.util.*;
public class Main {
// LCP 74. 最强祝福力场
public static void main(String[] args) {
Scanner scan = new Scanner(System.in); // 创建扫描器以读取输入
int m = scan.nextInt(), n = scan.nextInt(); // 读取所需的点数 m 和点的数量 n
int[][] points = new int[n][2]; // 创建二维数组存储点的坐标
for (int i = 0; i < n; i++) {
points[i] = new int[]{scan.nextInt(), scan.nextInt()}; // 读取每个点的坐标
}
int l = 0, r = (int) 1e9 + 5, ans = -1; // 初始化二分查找的左右边界和结果
while (l < r) { // 二分查找
int mid = l + r >> 1; // 计算中间值
if (check(points, mid, m)) ans = r = mid; // 如果可以找到至少 m 个重叠的点,更新右边界和结果
else l = mid + 1; // 否则更新左边界
}
// 输出结果,若 ans 为 -1 则输出 0,否则输出 ans
System.out.println(ans == -1 ? 0 : ans);
}
// 检查当前的 mid 是否能满足至少 m 个点的重叠
public static boolean check(int[][] points, int mid, int m) {
int n = points.length; // 获取点的数量
List<int[]> overlaps = new ArrayList<>(); // 存储重叠区域的坐标
// 最大强度必是每个正方形的交点
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 如果两个点的距离大于 2 * mid,则不考虑这两个点
if (Math.max(Math.abs(points[i][0] - points[j][0]), Math.abs(points[i][1] - points[j][1])) > 2 * mid) continue;
// 点 i 左上角坐标
int lx1 = points[i][0] - mid, ly1 = points[i][1] - mid;
// 点 i 右下角坐标
int rx1 = points[i][0] + mid, ry1 = points[i][1] + mid;
// 点 j 左上角坐标
int lx2 = points[j][0] - mid, ly2 = points[j][1] - mid;
// 点 j 右下角坐标
int rx2 = points[j][0] + mid, ry2 = points[j][1] + mid;
// 重叠部分左上角坐标
int ox1 = Math.max(lx1, lx2), oy1 = Math.max(ly1, ly2);
// 重叠部分右下角坐标
int ox2 = Math.min(rx1, rx2), oy2 = Math.min(ry1, ry2);
// 将重叠区域的四个角添加到 overlaps 列表中
overlaps.add(new int[]{ox1, oy1});
overlaps.add(new int[]{ox1, oy2});
overlaps.add(new int[]{ox2, oy1});
overlaps.add(new int[]{ox2, oy2});
}
}
// 遍历每个重叠区域,计算覆盖这些区域的点的数量
for (int[] overlap : overlaps) {
int cnt = 0; // 当前重叠区域覆盖的点数
for (int[] point : points) {
// 如果点在当前重叠区域内,则计数
if (Math.max(Math.abs(overlap[0] - point[0]), Math.abs(overlap[1] - point[1])) <= mid) cnt++;
}
// 如果覆盖的点数达到 m,则返回 true
if (cnt >= m) return true;
}
return false; // 否则返回 false
}
}
Go
package main
import (
"fmt"
)
var M, n int // M 为目标感染倍数,n 为幽匿催发体数量
var goast [][]int // 存储幽匿催发体的坐标
// 定义一个点的结构体
type point struct {
x, y int // x 和 y 坐标
}
func main() {
fmt.Scan(&M, &n) // 读取目标倍数 M 和幽匿催发体数量 n
var x, y int
for i := 0; i < n; i++ {
fmt.Scan(&x, &y) // 读取每个幽匿催发体的坐标
goast = append(goast, []int{x, y}) // 将坐标添加到列表中
}
// 二分查找
l := 0 // 左边界
r := int(1e9) // 右边界
res := -1 // 存储结果,初始化为 -1
for l < r {
mid := (l + r) / 2 // 计算中间值
if check(mid) { // 检查当前的 mid 是否可以达到目标 M
res = mid // 更新结果为当前 mid
r = mid // 更新右边界
} else {
l = mid + 1 // 更新左边界
}
}
if res == -1 {
fmt.Println(0) // 如果没有找到合适的结果,则输出 0
} else {
fmt.Println(res) // 输出找到的最小天数
}
}
// 检查当前的 mid 是否能满足至少 M 个幽匿催发体的重叠
func check(mid int) bool {
overlap := map[int]point{} // 存储重叠区域的坐标
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
// 如果两个幽匿催发体的距离大于 2 * mid,则跳过
if max(abs(goast[i][0]-goast[j][0]), abs(goast[i][1]-goast[j][1])) > 2*mid {
continue
}
// 计算幽匿催发体的影响区域
smallxi := goast[i][0] - mid
bigxi := goast[i][0] + mid
smallyi := goast[i][1] - mid
bigyi := goast[i][1] + mid
smallxj := goast[j][0] - mid
bigxj := goast[j][0] + mid
smallyj := goast[j][1] - mid
bigyj := goast[j][1] + mid
// 计算重叠区域的坐标
smallx := max(smallxi, smallxj)
bigx := min(bigxi, bigxj)
smally := max(smallyi, smallyj)
bigy := min(bigyi, bigyj)
// 将重叠区域的四个角添加到 overlap 映射中
var node point
node.x, node.y = smallx, smally
overlap[smallx*10+smally] = node
node.x, node.y = smallx, bigy
overlap[smallx*10+bigy] = node
node.x, node.y = bigx, smally
overlap[bigx*10+smally] = node
node.x, node.y = bigx, bigy
overlap[bigx*10+bigy] = node
}
}
// 遍历重叠区域,计算覆盖这些区域的幽匿催发体数量
for _, node := range overlap {
mcnt := 0 // 当前重叠区域覆盖的幽匿催发体数量
x := node.x
y := node.y
for i := 0; i < n; i++ {
// 如果点在当前重叠区域内,则计数
if max(abs(x-goast[i][0]), abs(y-goast[i][1])) <= mid {
mcnt += 1
if mcnt >= M { // 如果覆盖的幽匿催发体数量达到 M
return true // 满足条件,返回 true
}
}
}
}
return false // 否则返回 false
}
// 辅助函数:获取两个数中的最大值
func max(x, y int) int {
if x > y {
return x
}
return y
}
// 辅助函数:获取两个数中的最小值
func min(x, y int) int {
if x < y {
return x
}
return y
}
// 辅助函数:获取一个数的绝对值
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
Js
let w = []; // 存储幽匿催发体的坐标
function check(ps, mid) {
// 1. 统计所有左下和右上坐标
let xs = [], ys = [];
for (let i = 0; i < ps.length; i++) {
let p = ps[i];
let j = p[0], k = p[1]; // 获取幽匿催发体的坐标
xs.push(j - mid); // 记录左下角坐标
xs.push(j + mid); // 记录右上角坐标
ys.push(k - mid); // 记录左下角坐标
ys.push(k + mid); // 记录右上角坐标
}
// 2. 排序去重
xs = [...new Set(xs)].sort((a, b) => a - b); // 对 x 坐标进行去重和排序
ys = [...new Set(ys)].sort((a, b) => a - b); // 对 y 坐标进行去重和排序
// 3. 二维差分
let n = xs.length, m = ys.length; // 获取去重后坐标的长度
let diff = Array.from(Array(n + 2), () => new Array(m + 2).fill(0)); // 初始化差分数组
for (let i = 0; i < ps.length; i++) {
let p = ps[i];
let j = p[0], k = p[1]; // 获取幽匿催发体的坐标
// 查找当前坐标在去重数组中的位置
let r1 = binarySearch(xs, j - mid);
let r2 = binarySearch(xs, j + mid);
let c1 = binarySearch(ys, k - mid);
let c2 = binarySearch(ys, k + mid);
// 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 1
// 多 +1 是为了方便后续的复原
diff[r1 + 1][c1 + 1]++;
diff[r1 + 1][c2 + 2]--;
diff[r2 + 2][c1 + 1]--;
diff[r2 + 2][c2 + 2]++;
}
// 4. 直接在 diff 上复原,计算最大值
let ans = 0; // 存储最大重叠数量
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
// 复原差分数组,计算当前坐标的重叠数量
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
ans = Math.max(ans, diff[i][j]); // 更新最大重叠数量
}
}
return ans; // 返回最大重叠数量
}
// 二分查找函数,查找目标值在数组中的位置
function binarySearch(arr, target) {
let l = 0, r = arr.length - 1; // 初始化左右边界
while (l < r) {
let mid = Math.floor((l + r) / 2); // 计算中间值
if (arr[mid] >= target) { // 如果中间值大于等于目标值
r = mid; // 更新右边界
} else {
l = mid + 1; // 更新左边界
}
}
return l; // 返回目标值的位置
}
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
input += data; // 读取输入
return;
});
process.stdin.on('end', () => {
const lines = input.trim().split('\n'); // 按行分割输入
let m = Number(lines[0].trim()); // 读取目标倍数 M
let n = Number(lines[1].trim()); // 读取幽匿催发体数量 n
for (let i = 0; i < n; i++) {
let [x, y] = lines[i + 2].trim().split(' ').map(Number); // 读取每个幽匿催发体的坐标
w.push([x, y]); // 将坐标添加到列表中
}
let l = 0, r = 1e9; // 初始化二分查找的左右边界
while (l < r) {
let mid = Math.floor((l + r) / 2); // 计算中间值
if (check(w, mid) >= m) { // 检查是否可以满足条件
r = mid; // 更新右边界
} else {
l = mid + 1; // 更新左边界
}
}
console.log(l); // 输出结果
});