AcWing 5180. 正方形泳池


原题链接:5180. 正方形泳池 - AcWing题库

说实话题解和视频题解都不太好,有点过于复杂了,那就不得不记录一下我看视频题解衍生出的另一个较为简单的思路了。

根据答案形态出发,枚举所有这种形态找出最大值。

可以发现最大的泳池要么是左右边界被两棵树限制住了,或者就是上下边界被两棵树限制住了。
所以我们可以穷举所有两棵树的组合,并且以这两棵树y的差值或者x的差值为正方形的边长,来放下泳池。最大的泳池,必然在这些组合里面。

放下泳池有限制条件,假设以y的差值放下去,那么可用的连续x也必须大于等于y的差值,两棵树之间可能会有其他树来碍事,那么这里的x就会被断开成好几段,需要找出最大的那个x。

这种只有一棵树的,因为泳池不能超过边界,所以相当于外面围了一圈树,只要在四个角落种上树就好了。

AC代码

#include <bits/stdc++.h>
using namespace std;int N,T,ans=INT_MIN;
struct tree{int x,y;
}t[105];
vector<int>tmp;
bool cmpy(tree a,tree b){return a.y<b.y;
}
bool cmpx(tree a,tree b){return a.x<b.x;
}int main(){cin>>N>>T;for(int i=1;i<=T;++i)cin>>t[i].x>>t[i].y;t[++T]={0,0};t[++T]={0,N+1};t[++T]={N+1,0};t[++T]={N+1,N+1};sort(t+1,t+1+T,cmpy);for(int i=1;i<=T;++i){for(int j=i+1;j<=T;++j){tmp.push_back(0);tmp.push_back(N+1);for(int k=i+1;k<j;++k)tmp.push_back(t[k].x);sort(tmp.begin(),tmp.end());int xmax=INT_MIN;for(int k=0;k<tmp.size()-1;++k)xmax=max(xmax,tmp[k+1]-tmp[k]-1);ans=max(ans,min(xmax,t[j].y-t[i].y-1));tmp.clear();}}sort(t+1,t+1+T,cmpx);for(int i=1;i<=T;++i){for(int j=i+1;j<=T;++j){tmp.push_back(0);tmp.push_back(N+1);for(int k=i+1;k<j;++k)tmp.push_back(t[k].y);sort(tmp.begin(),tmp.end());int ymax=INT_MIN;for(int k=0;k<tmp.size()-1;++k)ymax=max(ymax,tmp[k+1]-tmp[k]-1);ans=max(ans,min(ymax,t[j].x-t[i].x-1));tmp.clear();}}cout<<ans<<endl;return 0;
}

思路很简单,但是说也不太说的明白。

重点:枚举所有答案形态。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Ubuntu18.04安装gdal3.4

一.依赖关系 所以&#xff0c;安装顺序&#xff1a;SQLite -> Proj -> Gdal

【AFL学习笔记(一)】简单的使用AFL进行漏洞挖掘测试

首先声明一点&#xff0c;ALF都是在Linux系统上运行 本文使用的是Ubuntu 20.4 版本进行演示 Step 1 下载afl-2.52b 官网地址afl2.52b 直接下载地址直接下载地址 下载完成之后在Ubuntu系统上进行解压&#xff1a; tar -afl-2.52b.tgzStep 2 创建测试用例 ①&#xff1a;创…

20 个有代码的 Python 脚本可使您的工作自动化

阿卜杜勒汉南哈桑 说明 在本文中&#xff0c;我们将探讨 20 个 Python 脚本及其代码&#xff0c;它们可以帮助您自动执行各种任务并提高工作效率。无论您是开发人员、数据分析师&#xff0c;还是只是希望简化工作流程的人&#xff0c;这些脚本都能满足您的需求。 目录 1. 简…

【软考-中级】系统集成项目管理工程师-配置管理历年案例

持续更新。。。。。。。。。。。。。。。 目录 2023 上 试题三(20分)2016 下 试题三(17分) 2023 上 试题三(20分) 某公司有自己的质量管理体系&#xff0c;其中配置管理程序已运行多年&#xff0c;由项目经理牵头组建变更控制委员会(CCB)&#xff0c;在创建配置管理环境后&…

数据库 MySql快速导入外部数据库流程

适用于新安装MySql本地没有数据情况 外部MySql数据库文件 任务管理器停用Mysql进程 将外部文件替换本地默认文件即可 重启电脑导入完成。

前端设计模式应应用场景

前端设计模式应应用场景 创建型模式(Creational Patterns)工厂模式单例模式原型模式 行为型模式(Behavioral Patterns)策略模式观察者模式/发布订阅模式迭代器模式状态模式 结构型模式(Structural Patterns)装饰器模式代理模式 创建型模式(Creational Patterns) 处理对象的创建…

填充颜色游戏

无语死了这题。 题目描述 小明最近迷上下面一款游戏。游戏开始时&#xff0c; 系统将随机生成一个 N N 的 正方形棋盘&#xff0c; 棋盘的每个格子都由六种颜色中的一种绘制。在每个步骤中&#xff0c; 玩家选择一种颜色&#xff0c; 并将与左上角连接的所有网格更改为该特…

树控件的使用

目录 1、修改树控件的基础属性&#xff1a; 2、准备图标 &#xff1a; &#xff08;1&#xff09;、ico后缀的图片放入当前文件路径的rc中 &#xff08;2&#xff09;、在Icon中添加资源&#xff0c;导入图片 &#xff08;3&#xff09;、准备HICON图标 &#xff08;4&am…

音频处理到雷达系统:滤波组的多领域应用 | 百能云芯

在电子元器件和电路设计领域&#xff0c;滤波组&#xff08;Filter Bank&#xff09;是一个关键概念&#xff0c;它用于处理和过滤信号&#xff0c;以满足各种应用的需求。云芯将带您深入研究滤波组在元器件中的应用&#xff0c;包括其工作原理、不同类型以及在通信、音频处理和…

qt 读取txt文本内容时,中文乱码

项目场景&#xff1a; 项目中&#xff0c;需要在TF卡中做类似txt阅读器的功能&#xff0c;因为app是在嵌入式系统下运行的&#xff0c;发现当读取txt的文本格式为ANSI时&#xff0c;中文的显示是乱码&#xff0c;故记录下解决方法 问题解决 中文乱码问题还是涉及到编码问题&…

【Unity】Unity开发微信小游戏(一)准备和了解工作

一、所需工具 0.Unity小游戏版本 如不使用此版本&#xff0c;则无法搜索到 InstantGame package 1.Unity插件&#xff1a;InstantGame package 此插件用于处理项目中的贴图、音频、网格、动画、场景等资源文件&#xff0c;保证小程序包体不会过大。 插件可以关联UOS服务&am…

百度智能云推出,国内首个大模型全链路生态支持体系

在10月17日举行的百度世界2023上&#xff0c;百度智能云宣布&#xff0c;百度智能云千帆大模型服务平台已服务17000多家客户&#xff0c;覆盖近500个场景。 同时&#xff0c;新的企业和开发者还正在不断地涌入千帆&#xff0c;大模型调用量高速攀升。平台上既有年龄仅14岁的小…

PAM从入门到精通(五)

接前一篇文章&#xff1a;PAM从入门到精通&#xff08;四&#xff09; 本文参考&#xff1a; 《The Linux-PAM Application Developers Guide》 先再来重温一下PAM系统架构&#xff1a; 更加形象的形式&#xff1a; 五、主要函数详解 3. pam_set_item 概述&#xff1a; 设置…

【定时开关机】windows 10 如何设置定时开关机

一、需求 二、场景 三、思路 四、实现 A. 设置来电开机 B. 设置及定时关机 一、需求 需要一台 win 10 的电脑在工作时间内自动开关机&#xff08;早 8:30 - 晚&#xff1a;6:05&#xff09; 二、场景 开机&#xff1a;早 8:30 关机&#xff1a;晚 6:05 三、思路 【开机…

目标跟踪数据集分享

360VOT: A New Benchmark Dataset for Omnidirectional Visual Object Tracking 360VOT 是一个新的大规模全景追踪基准数据集&#xff0c;旨在为全景视觉物体追踪提供支持。这个数据集包含了 120 个序列&#xff0c;总计超过 11.3 万张高分辨率帧&#xff0c;采用等距投影。追踪…

new Object()到底占用几个字节

Java内存模型 对象内存中可以分为三块区域&#xff1a;对象头(Header)&#xff0c;实例数据(Instance Data)和对齐填充(Padding)&#xff0c;以64位操作系统为例(未开启指针压缩的情况)Java对象布局 如下图所示&#xff1a; 其中对象头中的Mark Word中的详细信息在文章synchr…

李宏毅生成式AI课程笔记(持续更新

01 ChatGPT在做的事情 02 预训练&#xff08;Pre-train&#xff09; ChatGPT G-Generative P-Pre-trained T-Transformer GPT3 ----> InstructGPT&#xff08;经过预训练的GPT3&#xff09; 生成式学习的两种策略 我们在使用ChatGPT的时候会注意到&#xff0c;网站上…

JVM 垃圾回收机制(可达性分析、引用计数)

目录 1 什么是垃圾2 为什么需要回收3 哪些对象被判定为垃圾呢3.1 引用计数法3.2 可达性分析算法&#xff1a;GC Roots根 1 什么是垃圾 垃圾是指在运行程序中没有任何指针指向的对象&#xff0c;就是需要被回收的。 2 为什么需要回收 执行程序会不断地分配内存空间&#xff0c…

Windows安装SNMP服务

windows10安装SNMP服务 打开计算机的设置–应用–应用和功能–可选功能–点击加号添加功能,添加以下两个功能: windows server安装SNMP服务 搜索打开服务器管理器,点击功能–添加功能,勾选SNMP服务,点击下一步,等待安装完成 按win+R快捷键,运行service.msc,在服务中将…

与 Harbor 构建高效的镜像加速工作流

镜像是容器的基础&#xff0c;如今有很多用户在实践使用 Harbor 作为镜像存储与分发方案&#xff0c;本文介绍了 Harbor 在支持镜像加速方面的能力&#xff0c;以及 Nydus 这种改进的镜像格式&#xff0c;用于解决镜像在网络&#xff0c;存储&#xff0c;端到端可信方面的问题。…