首页 > 代码库 > 51nod 1275 连续子段的差异

51nod 1275 连续子段的差异

2024-09-19 04:54:46   217人阅读

技术分享

 

分析：

1、首先是尺取，尺取到每一个区间，区间满足这个条件，最大-最小<=k;

2、对于一个动态区间，怎么维护他的最大值，最小值（的下标）；——单调队列；

　　什么时候删掉头结点呢？ 当我找到了当前区间的上限；我需要尺取移动头结点了；此时，单调队列不用怕，只要这个头不影响我的单调队列，我就可以不用管；否则弹掉；

技术分享
 1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 const int maxn = 50000 + 5; 6 int a[maxn]; 7  8  9 int main()10 {11     int n,k;12     scanf("%d%d",&n,&k);13     for(int i=0;i<n;i++)14         scanf("%d",&a[i]);15 16     int ans = 0;17     deque<int> Amin,Amax;   //单调递减队列，单调递增队列18 19     for(int i=0,j=0;i<n;i++) {20 21         while(j<n) {22 23             while(!Amin.empty()&&a[j]>=a[Amin.back()])24                 Amin.pop_back();25 26             while(!Amax.empty()&&a[j]<=a[Amax.back()])27                 Amax.pop_back();28             Amin.push_back(j);29             Amax.push_back(j);30 31             if(a[Amin.front()]-a[Amax.front()]<=k)32                 j++;33             else break;34         }35         ans+=(j-i);36 37         if(Amin.front()==i)38             Amin.pop_front();39         if(Amax.front()==i)40             Amax.pop_front();41 42     }43     printf("%d\n",ans);44 45     return 0;46 }
View Code

 

51nod 1275 连续子段的差异


联系
我们