【备战秋招】每日一题:2023.04.26-华为OD机式-第三题-MC方块

在线评测链接:P1231

题目内容

MC最新版本更新了一种特殊的方块,幽匿催发体。这种方块能够吸收生物死亡掉落的经验并感染周围方块,使其变成幽匿块。Steve想要以此为基础尝试搭建一个经验仓库,他来到了创造超平坦模式,在只有草方块组成的平坦世界上进行他的实验。

在Steve的实验中,幽匿催发体可以看做每次吸收经验后会向自己平面方向上的周围八个方块进行感染,使其变成幽匿催发体。Steve任意选择了 n 个坐标点作为幽匿催发体的起始方块,接下来每天都会给予这些催发体足够使自身范围向外扩展一圈的经验。当有两个或以上的幽匿催发体的感染范围重叠时,重叠区域的方块会吸收更多的经验,吸收经验的数量为该方块所在不同幽匿催发体感染范围数量的整数倍。

如下方三张图所示,蓝色点A、B为初始幽匿催发体的位置

![img-vsSiykEJ-1687420811924)(/hw/P1231/1.png)]

第二天,向周围扩散感染

在这里插入图片描述

第三天,两个催发体的感染范围出现重叠,重叠部分的经验倍数 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

思路:二分答案+二维差分

二分答案

刷过一定量的二分答案题,我们就很容易发现这个题要求的答案<至少有一个方块的经验存储量的倍数可以达到给定的 M的天数>有单调性,即:

1.天数越久,就会有越多点重合。就越可能满足给定条件。

2.无限久后,一定会有点达到 M M M的重复。

如何写check函数?

直接数组模拟显然不行,因为平面太大了,二维数组开不了这么大。但是我们这个平面上有非常多的点是无用的 。我们把关键点(每个矩阵的左上角,右下角)提出来进行离散化,在一个更小的平面内进行二维差分即可。

知识点学习

没接触过离散化+二维差分的估计会觉得有些抽象,一些学习资料

1.一维差分:前缀和&差分 Oi-Wiki

2.二维差分:二维差分 知乎

3.二维坐标离散化:二维坐标离散化

tips:这是一道力扣杯的原题。见LCP 74.最强祝福力场 -灵神题解

类似题目推荐

一道比较有难度的二分答案题。要吃透这类题,需要多加练习!

初识二分答案

1.LeetCode 875. 爱吃香蕉的珂珂

2.LeetCode 2187. 完成旅途的最少时间

3.LeetCode 6325. 修车的最少时间

4.LeetCode 2226. 每个小孩最多能分到多少糖果

真题

P1236 美团实习-2023.04.15-第二题-分糖果

P1189. 华为实习 2023.04.12-实习笔试-第一题-购物系统的降级策略

P1006. 华为秋招 2022.9.21-数组取min

P1106. 腾讯音乐 2023.3.23-第二题-划分字符串

进阶练习

P1093. 米哈游 2023.03.19-第三题-塔子哥的无限字符串 - 二分答案 + 细节讨论

P1169 2023.04.08-美团春招-第四题-田地行走 - 二分答案 + 多源BFS

P1102 阿里巴巴 2023.03.21-第三题-数数 - 二分答案 + 数位dp

代码

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;
int check(vector<PII>& ps,int mid) 
{
        // 1. 统计所有左下和右上坐标
        vector<long long> xs, ys;
        for (auto &p: ps) {
            auto i = p.x;
            auto j = p.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());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        // 3. 二维差分
        int n = xs.size(), m = ys.size(), diff[n + 2][m + 2];
        memset(diff, 0, sizeof(diff));
        for (auto &p: ps) {
            auto i = p.x;
            auto j = p.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 上的数都加上 x
            // 多 +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;
    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){
            r=mid;
        }
        else l = mid + 1;
    }
cout << l << endl;
return 0;
}
// by yhy

python

M = int(input())
n = int(input())
c = []
for i in range(n):
    x, y = map(int, input().split())
    c.append((x, y))

def check(day):
    xs = set()
    ys = set()
    # 1. 统计所有左下和右上坐标
    for x, y in c:
        xs.add(x-day)
        xs.add(x+day)
        ys.add(y-day)
        ys.add(y+day)
    # 2. 排序去重
    xs = sorted(xs)
    ys = sorted(ys)
    xs_idx = {x:i+1 for i, x in enumerate(xs)}
    ys_idx = {x:i+1 for i, x in enumerate(ys)}
    
    # 二维差分
    diff = [[0] * (len(ys)+2) for _ in range(len(xs)+2)]
    for x, y in c:
        # 将区域 r1<=r<=r2 && c1<=c<=c2 上的数都加上 x
        # 多 +1 是为了方便求后面复原
        x_idx = xs_idx[x-day]
        x_idx_ = xs_idx[x+day]+1
        y_idx = ys_idx[y-day]
        y_idx_ = ys_idx[y+day]+1
        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]
min_x = min(c)[0]
max_y = max(c, key=lambda x: x[1])[1]
min_y = min(c, key=lambda x: x[1])[1]


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:
        r = mid
    elif tmp < M:
        l = mid+1
        
    else:
        r = mid
print(r)
# by mathcoder2

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();
        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;
            else l = mid + 1;
        }
        System.out.println(ans == -1 ? 0 : ans);
    }

    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++) {
                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.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++;
            }
            if (cnt >= m) return true;
        }
        return false;
    }
}

Go

package main

import (
	"fmt"
)

var M, n int
var goast [][]int

type point struct {
	x, y int
}

func main() {
	fmt.Scan(&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
	for l < r {
		mid := (l + r) / 2
		if check(mid) {
			res = mid
			r = mid
		} else {
			l = mid + 1
		}
	}
	if res == -1 {
		fmt.Println(0)
	} else {
		fmt.Println(res)
	}

}

func check(mid int) bool {
	overlap := map[int]point{}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			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)
			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 {
					return true
				}
			}
		}
	}
	return 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);
  ys = [...new Set(ys)].sort((a, b) => a - b);

  // 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 上的数都加上 x
    // 多 +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');
    // write your code here
    let m = Number(lines[0].trim().split(' '));
    let n = Number(lines[1].trim().split(' '));
    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);
});

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/31346.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

被测系统架构与数据流分析

开源项目litemall系统架构(https://github.com/linlinjava/litemall) 角色与数据用户产品前端技术栈后端技术栈数据存储 开源项目Mall的系统架构(https://github.com/macrozheng/mall) 角色与数据用户产品前端技术栈后端技术栈服务治理技术栈监控技术栈大数据处理技术栈数据存…

自动化测试工具 AirTest 的使用方法与简介

目录 前言&#xff1a; Airtest简介 1.基于图像识别的Airtest框架 2.基于UI识别的Poco框架 Airtest环境搭建 Airtest布局 Airtest使用步骤 第一步&#xff1a;连接移动设备 第二步&#xff1a;创建一个.air文件&#xff08;也就是我们的测试脚本&#xff09; 第三步&#xff1a…

【MySQL数据库 | 第二十篇】explain执行计划

目录 前言&#xff1a; explain&#xff1a; 语法&#xff1a; 总结&#xff1a; 前言&#xff1a; 上一篇我们介绍了从时间角度分析MySQL语句执行效率的三大工具&#xff1a;SQL执行频率&#xff0c;慢日志查询&#xff0c;profile。但是这三个方法也只是在时间角度粗略的…

如何在 XMind 中绘制流程图

XMind 是专业强大的思维导图软件,由于其结构没有任何限制,很多朋友特别喜欢用它来绘制流程图。禁不住大家的多次询问,今天 XMind 酱就将这简单的流程图绘图方法分享给大家。 在 XMind 中,绘制流程图的主角是「自由主题」和「联系」。它们可以打破思维导图的限制,让你自由…

Type-C PD显示器方案简介

方案概述 LDR6020 Type-C PD显示器方案可以给显示器提供一个全功能C口&#xff0c;支持手机&#xff0c;电脑&#xff0c;游戏主机等一线投屏功能&#xff0c;同时支持PD快充输出。LDR6020内置了 USB Power Delivery 控制器和 PD BMC PHY 收发器&#xff0c;支持PD2.0/3.0等快…

Java多线程与并发

1、JDK版本的选择 选择JDK8、JDK11进行讲解的原因&#xff1a;Oracle长期支持 2、进程和线程的区别 进程和线程的由来 3、进程与线程的区别 进程是资源分配的最小单位,线程是cpu调度的最小单位. 所有与进程相关的资源&#xff0c;都被记录在PCB(进程控制块)中。进程是抢占…

数学建模竞赛国赛入场券之攻略

数学建模竞赛国赛入场券之攻略 1.团队契合度 在3天的准备时间中&#xff0c;如果是临时组建的草台班子光处理分歧可能就已经耗掉一半时间&#xff0c;最好在赛前就完成磨合&#xff0c;像一起做模拟题练练手之类&#xff0c;甲准备图论、乙准备优化方法&#xff0c;然后再一块…

存储笔记8 ipsan

Module Objectives IP SAN的组件 IP SAN的好处 描述SAN中的IP融合及其影响 描述的基本架构 –iSCSI –FCIP –FCoE 讨论IP SAN技术的市场驱动因素 列出IP SAN技术 列出iSCSI的组件和连接选项 描述iSCSI体系结构和拓扑结构 解释iSNS操作 描述FCIP的体系结构 IP SAN互联…

Redis持久化机制与Redis事务

一、Redis 持久化机制 Redis 是个基于内存的数据库。那服务一旦宕机&#xff0c;内存中数据必将全部丢失。所以丢失数据的恢复对于 Redis 是十分重要的&#xff0c;我们首先想到是可以从数据库中恢复&#xff0c;但是在由 Redis 宕机时&#xff08;说明相关工作正在运行&#…

UDS系列-31服务(Routine Control)

诊断协议那些事儿 诊断协议那些事儿专栏系列文章,本文介绍例程控制服务RoutineControl,该服务的目的是Client端使用Routine Control服务来执行定义的步骤序列并获取特定序列的相关结果。这个服务经常在EOL、Bootloader中使用,比如,检查刷写条件是否满足、擦除内存、覆盖正…

Maven如何创建Maven web项目

1、创建一个新的模块: 1.1 使用骨架点一下&#xff0c;这里 1.2 找到maven-archetype-webapp项目&#xff0c;选中点击&#xff0c;一路next就行。 1.3 删除不必要的maven配置&#xff1a;&#xff08;这里我不需要&#xff0c;针对自己情况而定&#xff09; 可以从name这里开…

pr视频叠加,即原视频右上角添加另外一个视频方法,以及pr导出视频步骤

一、pr视频叠加&#xff0c;即原视频右上角添加另外一个视频方法 在使用pr制作视频时&#xff0c;我们希望在原视频的左上角或右上角同步播放另外一个视频&#xff0c;如下图所示&#xff1a; 具体方法为&#xff1a; 1、导入原视频&#xff0c;第一个放在v1位置&#xff0c;第…

案例 | 标杆引领!人大金仓智绘数字金融

随着中央数字经济政策推进金融业数字化建设&#xff0c;数字金融已初见成效&#xff0c;但尚存在信息安全缺乏保障、转型覆盖不全面等问题。 为实现金融行业全面数字化转型升级&#xff0c;作为数据库领域国家队&#xff0c;人大金仓紧跟国家战略&#xff0c;自主研发的系列数据…

采用SqlSugar的DBFirst相关功能创建数据库表对应的实体类

.NET Core官方教程中推荐使用的EF Core数据库ORM框架虽然能用&#xff0c;但是用起来并不是太方便&#xff08;或者是不习惯&#xff0c;之前用的最多的还是linq&#xff09;。之前下载的开源博客项目中使用的SqlSugar&#xff0c;后者是由果糖大数据科技团队维护和更新 &#…

【网络1】协议及相关命令

文章目录 1.局域网&#xff1a;CSMA/CD2.互联网&#xff1a;ARP&#xff0c;DHCP&#xff0c;NAT3.TCP协议&#xff1a;telnet&#xff0c;tcpdump&#xff0c;syn/accept队列4.HTTPS协议&#xff1a;摘要&#xff08;sha、md5、crc&#xff09;。win对文件MD5校验&#xff1a;…

C# NX二次开发:通过UFUN函数获取刀具描述,目录号,库号等信息

今天要将的是&#xff0c;在NX中对CAM模块进行二次开发的时候&#xff0c;往往需要获取一些关于刀具使用的信息&#xff0c;这些信息用NXOPEN的的方法录制也可以录制出来&#xff0c;但是录制出来的代码&#xff0c;往往都是一种刀具类型会出现一个Builder。这样在你不知道有多…

微服务开发系列 第十一篇:XXL-JOB

总概 A、技术栈 开发语言&#xff1a;Java 1.8数据库&#xff1a;MySQL、Redis、MongoDB、Elasticsearch微服务框架&#xff1a;Spring Cloud Alibaba微服务网关&#xff1a;Spring Cloud Gateway服务注册和配置中心&#xff1a;Nacos分布式事务&#xff1a;Seata链路追踪框架…

【AI】金融FinGPT模型

金融FinGPT模型开源&#xff0c;对标BloombergGPT&#xff0c;训练参数可从61.7亿减少为367万&#xff0c;可预测股价 继Bloomberg提出了500亿参数的BloombergGPT&#xff0c;GPT在金融领域的应用受到了广泛关注&#xff0c;但BloombergGPT是一个非开源的模型&#xff0c;而且…

RWA 成下一轮加密大叙事,PoseiSwap 的价值正在凸显

PoseiSwap是Nautilus Chain上的首个DEX&#xff0c;在Nautilus Chain模块化开发的支持下&#xff0c;PoseiSwap能够以更具延展性的方式来构建应用&#xff0c;并能够为交易者提供极佳的交易体验。基于Nautilus Chain支持下的Zk-Rollup方案&#xff0c;PoseiSwap构建了基于零知识…

cuda pyinstall cvs 使用记录

1.pip 换源 pip config set global.index-url https://mirrors.aliyun.com/pypi/simple/2.安装匹配cuda的pytorch 官网&#xff1a;PyTorch pip3 install torch torchvision torchaudio查看能否使用cuda: import torch torch.cuda.is_available()获得以下反馈&#xff1a; 意思…