题目大意

在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); // 输出结果
});