[USACO2012-Mar-Silver] Flowerpot 题解(单调队列 c++)

2023-10-27 19:36

本文主要是介绍[USACO2012-Mar-Silver] Flowerpot 题解(单调队列 c++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[USACO12MAR] Flowerpot S题解(单调队列 c++)

题目链接:[USACO2012-Mar-Silver] Flowerpot

题意:

  • 给你n个点,每个点有对应的x,y
  • 确认是否存在两个点,在 y 1 , y 2 y_1,y_2 y1,y2满足要求的情况下,输出最小的 ∣ x 2 − x 1 ∣ \lvert x_2 - x_1 \rvert x2x1

思路:

  • 如果暴力的话,我们就考虑对于每一个点,寻找其对应的 ∣ y 1 − y 2 ∣ > = D \lvert y_1-y_2 \rvert >= D y1y2>=D 的所有点,然后找最小的 ∣ x 2 − x 1 ∣ \lvert x_2 - x_1 \rvert x2x1
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>using namespace std;int ans = 0x3f3f3f3f;int main() {int n, d;cin >> n >> d;vector<vector<int>> v(n, vector<int>(2));for (int i = 0; i < n; i ++)cin >> v[i][0] >> v[i][1];sort(v.begin(), v.end());for (int i = 0; i < n; i ++){for (int j = i + 1; j < n; j ++) {if (v[j][1] - v[i][1] >= d)ans = min(ans, v[j][0] - v[i][0]);}}if (ans == 0x3f3f3f3f)cout << -1;elsecout << ans;return 0;
}
  • 暴力的时间复杂度为 O ( n 2 ) O(n^2) O(n2)
  • 不如我们这样想:首先把这些点按x坐标进行排序,令 l l l在这些点中进行遍历,对于每一个 l ∈ ( 1 , n ) l \in (1,n) l(1,n)我们都可以求出最小的 r r r,使得刚好在 [ l , r ] [l,r] [l,r]区间内恰好存在 ∣ y 1 − y 2 ∣ > = D \lvert y_1-y_2 \rvert >= D y1y2>=D的情况(区间 [ l , r − 1 ] [l,r-1] [l,r1]就不存在)
  • 这样问题就成了一个大小不固定的滑动窗口问题。我们使用队列q1的头结点存储从a[l].x开始y最大的值,q2存储最小值。
  • q1为例,若a[i+1]>a[i]a[i]没意义的。因为当r=i时还没有满足 ∣ y 1 − y 2 ∣ > = D \lvert y_1-y_2 \rvert >= D y1y2>=D。若$ y_{i+1}-y_j >= D(j<i+1) , 显然 a [ i ] 无意义,若 ,显然a[i]无意义,若 ,显然a[i]无意义,若 y_{i+1}-y_j >= D(j>i+1) , 我们求最小的 ,我们求最小的 ,我们求最小的\lvert x_2 - x_1 \rvert$,所以当a[i+1]在时,a[i]永无出头之日
  • 我们通过这种方式,遍历出每一个l时[l,r]中符合条件的 ∣ x 2 − x 1 ∣ \lvert x_2 - x_1 \rvert x2x1
代码如下
#include <iostream>
#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 1e6 + 10;PII a[N];// q1维护最大值(递减)  q中存储序号 
int q1[N], q2[N];
int h1 = 1, h2 = 1, t1, t2;
int ans = 0x3f3f3f3f;int main() {int n, d;cin >> n >> d;for (int i = 1; i <= n; i ++)cin >> a[i].first >> a[i].second;sort(a + 1, a + 1 + n);for (int l = 1, r = 0; l <= n; l ++) {while (h1 <= t1 && q1[h1] < l)		h1 ++;while (h2 <= t2 && q2[h2] < l)		h2 ++;while (a[q1[h1]].second - a[q2[h2]].second < d && r < n) {r ++;while (h1 <= t1 && a[q1[t1]].second < a[r].second)		t1 --;q1[++ t1] = r;while (h2 <= t2 && a[q2[t2]].second > a[r].second)		t2 --;q2[++ t2] = r;	}if (a[q1[h1]].second - a[q2[h2]].second >= d)ans = min(ans, abs(a[q1[h1]].first - a[q2[h2]].first));}if (ans == 0x3f3f3f3f)cout << -1;elsecout << ans;return 0;
}

这道题想了很长时间,如有讲的不清楚的地方,恳请大家批评指正

这篇关于[USACO2012-Mar-Silver] Flowerpot 题解(单调队列 c++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/287907

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下: