单调队列

发布 : 2020-06-26 分类 : 单调队列 浏览 :

用单调队列来解决问题,一般都是需要得到当前的某个范围内的最小值或最大值。

一篇详细的博客:传送门

例如:

Description
一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。

例如: 1, -3, 5, 1, -2, 3

当m=4时,sum = 5+1-2+3 = 7

当m=2或m=3时,sum = 5+1 = 6

Input
多测试用例,每个测试用例:

第一行是两个正数n, m ( n, m ≤ 300000 )

第二行是n个整数

Output
每个测试用例输出一行:一个正整数,表示这n个数的最大子序和长度

Sample Input
6 4
1 -3 5 1 -2 3

Sample Output
7

这道题可以用dp来解,也可以用单调队列。

方法一:(第一反应的做法,当然没有完全按照题目的输出,主要是用于检验)

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int a[300005];

int main(){
int n, m;
while(cin >> n >> m){
memset(a, 0, sizeof(a));
for(int i = 0; i < n; i++)
cin >> a[i];
int ans = 0, t = 0, temp = 0, len = 0, ans_l = 0, ans_t = 0;
while(t + len < n){
for(int i = t; i < t + m; i++){
temp += a[i];
len++;
if(ans < temp){
ans = temp;
ans_l = len;
ans_t = t;
}
}
t++;
len = 0; temp = 0;
}
cout << "start: " << ans_t << " " << "length: " << ans_l << endl;
cout << ans << endl;
}
return 0;
}

方法二:(单调队列)

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
//跟前缀和差不多
#include <iostream>
#include <algorithm>
#include <cstring>
#include <list>
using namespace std;

#define MIN -0x7fffffff
int sum[300005];
list <int> L;

int main(){
int n, m;
while(cin >> n >> m){
memset(sum, 0, sizeof(sum));
sum[0] = 0; //注意:这里一定要从sum[1]开始存储,并且设置sum[0] = 0,原因可以从下面的for循环和两个while循环推出
cin >> sum[1];
for(int i = 2; i <= n; i++){
cin >> sum[i];
sum[i] += sum[i - 1];
}
L.clear();
int ans = MIN;
L.push_front(0); //将下标i入队
for(int i = 1; i <= n; i++){
while(!L.empty() && i - L.back() > m){ //判断是否在范围(i-m,i)内,不在就pop
L.pop_back();
}
ans = max(ans, sum[i] - sum[L.back()]); //求最大值,sum[i]-sum[min],表示前i个中找到最小的来减,sum[min]就是单调队列的尾部sum[L.back()]
while(!L.empty() && sum[i] < sum[L.front()]){ //更新单调队列,比sum[i]大的值都去掉
L.pop_front();
}
L.push_front(i); //最后将下标i入队
}
cout << ans << endl;
}
return 0;
}

/*
Input:
9 5
3 7 -2 9 -9 6 5 -4 7
6 4
1 -3 5 1 -2 3
Output:
17
7
*/
本文作者 : preccrep
原文链接 : https://preccrep.github.io/2020/06/26/%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97/
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
留下足迹

博客已萌萌哒运行(●'◡'●)ノ♥
Theme - BMW | Made With 💗 | Powered by GodBMW