单调队列
定义
单调队列，就是指队列中的元素是单调的。
$a_1,a_2,a_3,…,a_n$满足$a1\leq a_2\leq a_3…\leq a_n$的序列便是单调序列。
运用单调队列可以简化问题，由于队列是单调的，那么我们存取最大最小值的复杂度均是$O(1)$。而每一个元素入队一次，出队一次的复杂度也是$O(1)$。
而单调队列和数据结构deque结合较好，如果题目的数据量不是很大，没有卡std，就可以使用deque实现。
维护
以单调增序列为例子：
- 如果队列长度一定，先判断队首元素是否在规定范围内，如果超范围就弹出队首。
- 每次加入元素和队尾比较，如果当前元素小于队尾元素并且队列非空，就弹出队尾指针，直到满足单调性为止。
(题目太老，只能换个改版的。代码有一定问题，细心的人能看下出来。)
题解
建两个单调队列，寻找两个最小值加入其中一个堆中，有点像haffman编码的方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define pb push_back
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 10;
int n,ans;
int a[maxn];
int T;
int main(){
#ifdef LOCAL
freopen("111.in","r",stdin);
#endif
scanf("%d",&n);
rep(i,0,n){
scanf("%d",&a[i]);
}
deque<int> dq1;
deque<int> dq2;
sort(a,a+n);
rep(i,0,n) dq1.pb(a[i]);
ans = 0;
int x,y;
rep(i,0,n-1){
if(dq2.empty()){
x = dq1.front();
dq1.pop_front();
}else if(dq1.empty()){
x = dq2.front();
dq2.pop_front();
}else{
if(dq1.front() < dq2.front()){
x = dq1.front(),dq1.pop_front();
}else{
x = dq2.front(),dq2.pop_front();
}
}
if(dq2.empty()){
y = dq1.front();
dq1.pop_front();
}else if(dq1.empty()){
y = dq2.front();
dq2.pop_front();
}else{
if(dq1.front() < dq2.front()){
y = dq1.front(),dq1.pop_front();
}else{
y = dq2.front(),dq2.pop_front();
}
}
ans += (x+y);
dq2.pb(x+y);
}
printf("%d\n",ans);
return 0;
}
|
题解
单调队列+维护一下队头指针不能超过$k$的范围。
由于有最大值和最小值，维护两个单调队列。
需要注意一下的就是如果是手写双向队列的话，我一般是定义
1
2
3
4
5
| int st,ed;
st = ed = 0;
mmax[ed++] = a[0];
while(st<ed && mmax[ed-1]<=a[i]) ed--;
|
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n,k;
int a[maxn];
int mmax[maxn];
int mmin[maxn];
int main(){
#ifdef LOCAL
freopen("12.in","r",stdin);
#endif
scanf("%d%d",&n,&k);
rep(i,0,n) scanf("%d",&a[i]);
int st1,st2,ed1,ed2;
st1 = st2 = ed2 = ed1 = 0;
mmax[ed1++] = 0; mmin[ed2++] = 0;
rep(i,0,k-1){
while(st1<ed1 && a[mmax[ed1-1]] <= a[i]) ed1--;
mmax[ed1++] = i;
while(st2<ed2 && a[mmin[ed2-1]] >= a[i]) ed2--;
mmin[ed2++] = i;
}
rep(i,k-1,n){
while(st2<ed2 && i-mmin[st2]+1 > k) st2++;
while(st2<ed2 && a[mmin[ed2-1]] >= a[i]) ed2--;
mmin[ed2++] = i;
printf("%d%c",a[mmin[st2]],i==n-1?'\n':' ');
}
rep(i,k-1,n){
while(st1<ed1 && i-mmax[st1]+1 > k) st1++;
while(st1<ed1 && a[mmax[ed1-1]] <= a[i]) ed1--;
mmax[ed1++] = i;
printf("%d%c",a[mmax[st1]],i==n-1?'\n':' ');
}
return 0;
}
|
题意
给定一个序列，求不超过$k$长的最大连续子段和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int T,n,k;
const int maxn = 1e5 + 123;
int a[maxn*3];
int b[maxn];
int main(){
#ifdef LOCAL
freopen("11.in","r",stdin);
#endif
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
rep(i,0,n) scanf("%d",&b[i]);
rep(i,1,n*2+1) a[i] = (a[i-1] + b[(i-1)%n]);
deque<int> dq;
int ans = -INF;
int l,r;
rep(i,1,2*n+1){
while(!dq.empty() && i-dq.front() > k) dq.pop_front();
while(!dq.empty() && a[dq.back()] > a[i-1]) dq.pop_back();
dq.push_back(i-1);
int temp = a[i] - a[dq.front()];
if(ans < temp){
ans = temp;
l = dq.front()+1; r = i;
if(r>n) r-=n;
}
}
printf("%d %d %d\n",ans,l,r);
}
return 0;
}
|
题意
给定一段序列，求最长的一段子序列，他的条件是
题解
建立两个单调队列，维护$i$之前最大值的下标和$i$之前最小值的下标。
- 如果最大值最小值超过$k$就弹出下标较小的，并记录较小的位置。
答案是$i-pos$，如果之后的点满足条件了，那么说明$[pos+1,n]$是满足条件的，因为e.g.$a[min[st] 到min[st+1]]$中的元素都大于$a[min[st+1]]$，如果$a[min[st+1]]$满足那么，$a[min[st]+1]$肯定满足条件。
心路历程：我真是太弱了，这就是一道基础的单调队列题目，我想到用两个单调队列来维护，但是对于小于$k$和大于$m$这个条件，不知道怎么去掌控，妈蛋，其实可以靠单调队列的单调性来掌控他们之间的差距。因为一个是递增一个是递减，如果他们之间的差距过大，那么就可以pop掉队首元素，来减少他们的差距，那么大于$m$怎么维护呢？那就是特判他们之间差距是否大于$m$,大于的话就更新一下答案。对于每个$i$就是维护了他之前最大的值的下标和最小值的下标。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n,m,k;
const int maxn = 1e5 + 10;
int a[maxn];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
while(~scanf("%d%d%d",&n,&m,&k)){
rep(i,1,n+1) scanf("%d",&a[i]);
deque<int> dq1;
deque<int> dq2;
int ans = 0;int pos = 0;
rep(i,1,n+1){
while(!dq1.empty() && a[dq1.back()]>=a[i]) dq1.pop_back();
dq1.push_back(i);
while(!dq2.empty() && a[dq2.back()]<=a[i]) dq2.pop_back();
dq2.push_back(i);
while(!dq1.empty() && !dq2.empty() && a[dq2.front()]-a[dq1.front()]>k){
if(dq1.front() < dq2.front())
pos = dq1.front(),dq1.pop_front();
else
pos = dq2.front(),dq2.pop_front();
}
if(!dq1.empty() && !dq2.empty() && a[dq2.front()]-a[dq1.front()] >=m)
ans = max(ans,i-pos);
}
printf("%d\n",ans);
}
return 0;
}
|
题意
股票交易
- $i$天你可以以$APi$价格买入股票，$BPi$价格卖出股票
- $i$天最多买$ASi$股，最多卖$BSi$股
- 最多拥有$MaxP$股股票
- 交易后有缓冲期$M$天
开始无限制的钱，问最多能赚多少钱？
题解
AC代码
http://www.voidcn.com/article/p-bcrxdtjx-nd.html
