服装设计有哪些网站,wordpress 官网模板,网页加速器浏览器,网站主题的分类[USACO12MAR] Flowerpot S题解(单调队列 c)
题目链接#xff1a;[USACO2012-Mar-Silver] Flowerpot
题意#xff1a;
给你n个点#xff0c;每个点有对应的x,y确认是否存在两个点#xff0c;在 y 1 , y 2 y_1,y_2 y1,y2满足要求的情况下#xff0c;输出最小的 ∣ x …[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 ∣x2−x1∣
思路
如果暴力的话我们就考虑对于每一个点寻找其对应的 ∣ y 1 − y 2 ∣ D \lvert y_1-y_2 \rvert D ∣y1−y2∣D 的所有点然后找最小的 ∣ x 2 − x 1 ∣ \lvert x_2 - x_1 \rvert ∣x2−x1∣
#include iostream
#include vector
#include deque
#include algorithmusing namespace std;int ans 0x3f3f3f3f;int main() {int n, d;cin n d;vectorvectorint v(n, vectorint(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 ∣y1−y2∣D的情况(区间 [ l , r − 1 ] [l,r-1] [l,r−1]就不存在)这样问题就成了一个大小不固定的滑动窗口问题。我们使用队列q1的头结点存储从a[l].x开始y最大的值q2存储最小值。以q1为例若a[i1]a[i]则a[i]没意义的。因为当ri时还没有满足 ∣ y 1 − y 2 ∣ D \lvert y_1-y_2 \rvert D ∣y1−y2∣D。若$ y_{i1}-y_j D(ji1) , 显然 a [ i ] 无意义若 ,显然a[i]无意义若 ,显然a[i]无意义若 y_{i1}-y_j D(ji1) , 我们求最小的 ,我们求最小的 ,我们求最小的\lvert x_2 - x_1 \rvert$所以当a[i1]在时a[i]永无出头之日我们通过这种方式遍历出每一个l时[l,r]中符合条件的 ∣ x 2 − x 1 ∣ \lvert x_2 - x_1 \rvert ∣x2−x1∣
代码如下
#include iostream
#include algorithmusing namespace std;typedef pairint, 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;
}这道题想了很长时间如有讲的不清楚的地方恳请大家批评指正
