MT3045 松鼠接松果

思路:

求x的一个区间,使区间中的松果的最大y坐标和最小y坐标的差至少为D。若有多个区间,则取最小的那个。

即使用单调队列不断维护最大值和最小值。

首先L固定不动,R不断右移:

即若函数f(R)=max[L,R]-min[L,R] >=D,则此区间满足要求。

之后L往右移一位,R不断右移,找下一个满足条件的区间。

代码: 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, d, ans = 0x3f3f3f3f;
struct pos
{
    int x, y;
    bool operator<(const pos &a) const
    {
        return x < a.x;
    }
} p[N];
deque<int> maxn, minn;//存储最大值和最小值的索引
int main()
{
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].x >> p[i].y;
    }
    sort(p + 1, p + n + 1); 
    int l = 1;              // 左端点从1开始
    for (int i = 1; i <= n; i++)
    {
        // 确保maxn队列中的y坐标是递增的
        while (!maxn.empty() && p[i].y > p[maxn.back()].y)
            maxn.pop_back();
        maxn.push_back(i);
       // 确保minn队列中的y坐标是递减的
        while (!minn.empty() && p[i].y < p[minn.back()].y)
            minn.pop_back();
        minn.push_back(i);
        //如果满足条件,就更新答案
        while (l < i && p[maxn.front()].y - p[minn.front()].y >= d)
        {
            ans = min(ans, p[i].x - p[l].x);
            l++;
           
            while (!maxn.empty() && maxn.front() < l)
                maxn.pop_front();   
            
            while (!minn.empty() && minn.front() < l)
                minn.pop_front();
        }
    }
    if (ans == 0x3f3f3f3f)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}

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

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

相关文章

Pytest框架中用例用例执行常用参数介绍

pytest 支持通过命令行参数来定制测试运行的方式。以下是一些常用的 pytest 执行参数介绍。 学习目录 -q 或 --quiet: 安静模式&#xff0c;只显示进度和摘要 -s : 选项允许在测试的输出中捕获 stdout 和 stderr。 -v : 选项会使 pytest 的输出更加详细。 -k &#xff1a;…

数据分析必备:一步步教你如何用Pandas做数据分析(15)

1、Pandas 数据丢失 Pandas 数据丢失的操作实例 在现实生活中&#xff0c;数据丢失始终是一个问题。机器学习和数据挖掘等领域在模型预测的准确性方面面临严重问题&#xff0c;因为缺少值会导致数据质量较差。在这些领域中&#xff0c;缺失值处理是使模型更准确和有效的主要重…

godot.bk2

1.$node_name 其实 就是 get_node 的语法糖 2.场景内部用get_node&#xff0c;场景外部用信号 这是自定义信号的绑定&#xff0c;如果是内置信号&#xff0c;直接右键点击链接到一个函数即可 3.场景切换和摄像头一直居中 4.class_name命名一个类&#xff0c;extends继承&…

【TB作品】MSP430F149,ADC采集,光强GY-30,DS18B20温度采集

功能 读取了GY-30 DS18B20 P6.0ADC P6.1ADC 显示到了LCD12864 硬件 //GY30 //SCL–P1.0 //SDA–P1.1 //VCC–3.3V //GND–GND //ADDR–不接 //DS18B20 //DATA–P1.6 //VCC–3.3V //GND–GND //ADC //DATA–P1.6 //P6.0 P6.1 ADC输入口 部分程序 #include <msp430.h>…

碰撞检测技术在AI中的重要作用

引言&#xff1a; 随着人工智能技术的不断发展&#xff0c;AI已经渗透到我们生活的方方面面。在游戏、机器人、虚拟现实等领域中&#xff0c;碰撞检测技术扮演着至关重要的角色。本文将探讨碰撞检测技术在AI中的作用&#xff0c;以及如何利用这项技术来改善AI系统的性能和用户体…

网络空间安全数学基础·环

4.1 环与子环 &#xff08;理解&#xff09; 4.2 整环、除环、域 &#xff08;熟练&#xff09; 4.3 环的同态、理想 &#xff08;掌握&#xff09; 4.1 环与子环 定义&#xff1a;设R是一非空集合&#xff0c;在R上定义了加法和乘法两种代数运算&#xff0c; 分别记为ab和a…

考研数学:有些无穷小不能用等价无穷小的公式?

今天要给大家分享的笔记是&#xff1a;《有些无穷小虽然是无穷小&#xff0c;但却不能用无穷小的相关公式》&#xff1a;

MySQL(十一) 用户管理

1.用户 1.1 用户信息 MySQL中的用户&#xff0c;都存储在系统数据库mysql的user表中 mysql> select host,user,authentication_string from user; --------------------------------------------------------------------- | host | user | authentication…

重载运算符C++---学习笔记

一、笔记 1. 重载运算符基础知识 重载运算符进行的运算和普通数的加减运算不同之处在于重载运算符的操作数为一个一个自定义的对象&#xff0c;所以相应的要对普通的运算符如-*%/的调用方法进行重写&#xff0c;重载的本质还是函数调用 2. 重载运算符的语法 重载运算符的语…

Python PyInstaller打包方法介绍

为了将开发好的Python工具交付给其他人使用&#xff0c;除了在目标电脑部署Python编译环境以外&#xff0c;我们还可以将它打包成可执行文件&#xff0c;这样目标电脑不需要安装Python环境就可以运行。将Python程序打包成可执行文件的方法有多种&#xff0c;比如Nuitka、PyInst…

Java基础教程:算术运算符快速掌握

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。运营社区&#xff1a;C站/掘金/腾讯云&#xff1b;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一…

基于HTML+CSS制作感恩,传统节日,感恩节【网页设计】

一、&#x1f468;‍&#x1f393;网站题目 &#x1f967; 感恩、&#x1f370;传统节日、&#x1f990;地方美食小吃文化、&#x1f37a;餐饮文化、等网站的设计与制作。 二、✍️网站描述 &#x1f367;感恩主题网站 主要对各种感恩进行展示&#xff0c;让浏览者清晰地了解…

c++初试

c初试 字符串的使用和bool类型 定义自己的命名空间my_sapce&#xff0c;在my_sapce中定义string类型的变量s1&#xff0c;再定义一个函数完成对字符串的逆置。 #include <iostream>using namespace std; namespace my_sapce {string s1 "abcdefg";void Inve…

基于字典树可视化 COCA20000 词汇

COCA20000 是美国当代语料库中最常见的 20000 个词汇&#xff0c;不过实际上有一些重复&#xff0c;去重之后大概是 17600 个&#xff0c;这些单词是很有用&#xff0c;如果能掌握这些单词&#xff0c;相信会对英语的能力有一个较大的提升。我很早就下载了这些单词&#xff0c;…

CPVT(ICLR 2023)论文解读

paper&#xff1a;Conditional Positional Encodings for Vision Transformers official implementation&#xff1a;GitHub - Meituan-AutoML/CPVT 存在的问题 位置编码的局限性&#xff1a;传统Transformer中的绝对位置编码&#xff08;无论是可学习的还是固定的&#xff…

“世界酒中国菜”系列活动如何助推乡村振兴和文化交流?

"世界酒中国菜"系列活动如何助推乡村振兴和文化交流&#xff1f; 《经济参考报》&#xff08;2024年5月24日 第6版&#xff09; 新华社北京&#xff08;记者 张晓明&#xff09; “世界酒中国菜”系列活动自启动以来&#xff0c;已在国内外产生了广泛影响。这一国家…

6,串口编程———通过串口助手发送数据,控制led亮灭

//功能&#xff1a;串口助手每次发送数据格式&#xff1a;0000& // 第二个字节控制LED1亮灭 // 第三个字节控制LED2亮灭 // 第四个字节控制LED3亮灭 // 第无个字节控制LED4亮灭 //要求&#xff1a;代码能够一直运行&#xff0c;能够接收多字节数据 上节讲了串口的基本…

生态融合促发展 YashanDB与丰图科技完成兼容性认证

近日&#xff0c;深圳计算科学研究院崖山数据库系统YashanDB V23与丰图科技智域城市数字孪生平台顺利完成兼容性互认证。经严格测试&#xff0c;双方产品完全兼容&#xff0c;稳定运行&#xff0c;充分满足企事业单位在高性能、高可用性、高稳定性及高可控性方面的核心需求&…

【Linux系统编程】冯诺依曼体系、操作系统、进程的认识

目录 一、认识冯诺依曼体系 二、认识操作系统 三、认识进程 一、认识冯诺依曼体系 我们日常使用的计算机&#xff0c;笔记本和我们不常见的计算机如服务器&#xff0c;它们都遵循冯诺依曼体系。 下图是冯诺依曼体系结构的图解&#xff1a; 我们可以看到冯诺依曼体系结构由…

String,StringBuffer ,StringBuilder 的区别及其详解

目录 一、String1.1 String介绍1.2 深入理解String的不可变性1.3 String 操作字符串方法 二、StringBuffer2.1 StringBuffer介绍2.2 StringBuffer 构造方法2.3 StringBuffer 常用方法 三、StringBuilder2.1 StringBuffer介绍 四、String&#xff0c;StringBuffer &#xff0c;S…