A214.子矩阵
2026-04-13 18:07:15
发布于：广东
P13889 [蓝桥杯 2023 省 Python A] 子矩阵
洛谷原题，链接：https://www.luogu.com.cn/problem/P13889
思路：
核心问题
给定 n 个二维点 (x, y) 和一个整数 d，要求找到一个点的子集，满足子集中 y 的最大值 - y 的最小值 ≥ d，且该子集的x 的最大值 - x 的最小值尽可能小，输出这个最小的 x 差值；若不存在满足条件的子集，输出-1。
核心算法框架
排序 + 滑动窗口（双指针） + 两个单调队列，是解决这类带最值约束的区间最小差值问题的经典最优解法，整体时间复杂度O(nlogn)（排序主导），适配n≤105的大数据规模（代码中N=100010）。
1. 基础工具：快速读入函数read
void read(int &x){
int f=1;x=0;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}
x*=f;
}
手写getchar版快速输入，比cin/cout快数倍，避免大数据量下的输入超时；
支持处理负数（本题中 x/y 应为正，不影响）。
2.变量与结构体定义
#define N 100010
int n,d,ans;
struct node{int x,y;}a[N];
bool cmp(node aa,node bb){return aa.x<bb.x;}
int p1[N],p2[N];
int head1,head2,tail1,tail2;
p1：维护窗口内 y 的最大值的单调递减队列（队头是 y 最大的点的下标）；
p2：维护窗口内 y 的最小值的单调递增队列（队头是 y 最小的点的下标）。
- 预处理：按 x 升序排序
sort(a+1,a+1+n,cmp);
核心关键步骤：排序后，任意区间[le, r]的 x 差值为a[r].x - a[le].x，且x 差值随 r 增大而增大、随 le 增大而减小，为后续滑动窗口（双指针） 提供单调性基础，保证能找到最小 x 差值。
- 初始化
ans=0x3f3f3f3f;
head1=head2=1;
int le=0,r=0;
5.核心：滑动窗口 + 单调队列维护（外层遍历左边界 le）
for(int le=0;le<=n;le++){
while(head1<=tail1&&p1[head1]<le) head1++;
while(head2<=tail2&&p2[head2]<le) head2++;
while(a[p1[head1]].y-a[p2[head2]].y< d && r<n){
r++;
while(head1<=tail1&&a[p1[tail1]].y<a[r].y) tail1--;
p1[++tail1]=r;
while(head2<=tail2&&a[p2[tail2]].y>a[r].y) tail2--;
p2[++tail2]=r;
}
if(r!=n) ans=min(ans,a[r].x-a[le].x);
}
这是代码的核心，分3个关键动作，所有操作均为线性 O (n)，无嵌套冗余
动作 1：清理队列的过期队头
队列中存的是点的下标，若下标<le，说明该点已在当前窗口[le, r]外，直接弹出队头，保证队列中仅保留窗口内的点。
动作 2：扩展右边界 r，直到满足约束
当当前窗口内的y最大值 - y最小值 < d（不满足条件），且 r 未遍历完所有点时，将 r 右移并加入两个单调队列，单调队列的维护规则：
最大队列 p1（单调递减）：新点 r 的 y 比队尾大时，队尾的点永远不可能成为后续窗口的 y 最大值，直接弹出；直到队尾 y≥a [r].y，再将 r 加入队尾，保证队头始终是窗口内 y 最大的点。
最小队列 p2（单调递增）：新点 r 的 y 比队尾小时，队尾的点永远不可能成为后续窗口的 y 最小值，直接弹出；直到队尾 y≤a [r].y，再将 r 加入队尾，保证队头始终是窗口内 y 最小的点。
动作 3：更新最小 x 差值当停止扩展 r 时，若 r≠n（说明找到满足条件的窗口），此时窗口[le, r]的 x 差值为a[r].x - a[le].x，用该值更新全局最小 ans。
6. 结果输出
if(ans>=0x3f3f3f3f){printf("-1");return 0;}
else{printf("%d",ans);}
若 ans 仍为初始的无穷大，说明遍历完所有窗口都未找到满足y最大-y最小≥d的子集，输出-1；
否则输出最小的 x 差值 ans。
关键细节与算法优势
-
单调队列的核心作用
避免对每个窗口重新遍历求 y 的最大 / 最小值（暴力法O(n2)），通过O (1) 获取窗口最值，将滑动窗口的时间复杂度从O(n2)降至O(n)。 -
双指针的单调性
因为点按 x 升序排序，左边界 le 右移时，右边界 r 不会左移，le 和 r 各仅遍历 n 次，保证线性复杂度。
3.** 下标统一**
代码中点的下标是 1~n，双指针 le/r 是 0~n，队列存储的是点的 1 维下标，边界判断清晰，无越界风险。
- 时间复杂度
排序：O(n log n)（主导复杂度）；
滑动窗口 + 单调队列：O(n)（每个点入队 / 出队各一次）；
整体：O(n log n)，完美适配n≤105的评测用例。
7.总结
将二维约束问题（x 最小差 + y 最值差≥d）通过按 x 排序转化为一维滑动窗口问题，再用两个单调队列分别维护窗口内 y 的最大 / 最小值，最终在最优时间内找到答案
最终代码：
#include<bits/stdc++.h>
using namespace std;
void read(int &x){
int f=1;x=0;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}
x*=f;
}
#define N 100010
int n,d,ans;
struct node{
int x,y;
}a[N];
bool cmp(node aa,node bb){
return aa.x<bb.x;
}
int p1[N],p2[N];
int head1,head2,tail1,tail2;
int main(){
read(n),read(d);
for(int i=1;i<=n;i++){
read(a[i].x),read(a[i].y);
}
sort(a+1,a+1+n,cmp);
ans=0x3f3f3f3f;
head1=head2=1;
for(int le=0,r=0;le<=n;le++){
while(head1<=tail1&&p1[head1]<le) head1++;
while(head2<=tail2&&p2[head2]<le) head2++;
while(a[p1[head1]].y-a[p2[head2]].y< d && r<n){
r++;
while(head1<=tail1&&a[p1[tail1]].y<a[r].y) tail1--;
p1[++tail1]=r;
while(head2<=tail2&&a[p2[tail2]].y>a[r].y) tail2--;
p2[++tail2]=r;
}
if(r!=n) ans=min(ans,a[r].x-a[le].x);
}
if(ans>=0x3f3f3f3f){
printf("-1");return 0;
}
else{
printf("%d",ans);
}
}
完结撒花
团队招人：https://www.acgo.cn/application/1811737919264829440
有帮助，赞一个