poj2823

15 9月 2015

Sliding Window

An array of size n ≤ 10⁶ is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position	Minimum value	Maximum value
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

8 3

1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3

3 3 5 5 6 7

Source

POJ Monthly--2006.04.28, Ikki

题目类型：单调队列

算法分析：这是一道使用单调队列解决的经典问题。维护一个严格单调增和一个严格单调减队列，重点是判断队头元素何时出队列，方法是向队列中添加元素的同时将元素的下标也添加进去，之后直接比较下标之间的关系即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const int MOD = 32767;

const int maxn = 1000000 + 66;

struct Node
{
    int val, id;
};

Node ans[maxn], out_inq[maxn], out_deq[maxn];
int inq_len, deq_len;

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int n, k;

    while (scanf ("%d%d", &n, &k) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf ("%d", &ans[i].val);
            ans[i].id = i;
        }

        deque <Node> inq, deq;

        for (int i = 1; i <= k; i++)
        {
            while (!inq.empty () && inq.back ().val <= ans[i].val)
                inq.pop_back ();

            inq.push_back (ans[i]);

            while (!deq.empty () && deq.back ().val >= ans[i].val)
                deq.pop_back ();

            deq.push_back (ans[i]);
        }

        inq_len = deq_len = 0;
        out_inq[inq_len++] = inq.front ();
        out_deq[deq_len++] = deq.front ();

        for (int i = k + 1; i <= n; i++)
        {
            if (inq.front ().id + k == ans[i].id)
                inq.pop_front ();

            while (!inq.empty () && inq.back ().val < ans[i].val)
                inq.pop_back ();

            inq.push_back (ans[i]);
            out_inq[inq_len++] = inq.front ();

            if (deq.front ().id + k == ans[i].id)
                deq.pop_front ();

            while (!deq.empty () && deq.back ().val >= ans[i].val)
                deq.pop_back ();

            deq.push_back (ans[i]);
            out_deq[deq_len++] = deq.front ();
        }

        for (int i = 0; i < deq_len; i++)
        {
            if (i == 0)
                printf ("%d", out_deq[i].val);

            else
                printf (" %d", out_deq[i].val);
        }
        puts ("");


        for (int i = 0; i < inq_len; i++)
        {
            if (i == 0)
                printf ("%d", out_inq[i].val);

            else
                printf (" %d", out_inq[i].val);
        }

        puts ("");

    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const int MOD = 32767;

const int maxn = 1000000 + 66;

struct Node

{

int val, id;

};

Node ans[maxn], out_inq[maxn], out_deq[maxn];

int inq_len, deq_len;

int main()

{

// freopen ("aaa.txt", "r", stdin);

int n, k;

while (scanf ("%d%d", &n, &k) != EOF)

{

for (int i = 1; i <= n; i++)

{

scanf ("%d", &ans[i].val);

ans[i].id = i;

}

deque <Node> inq, deq;

for (int i = 1; i <= k; i++)

{

while (!inq.empty () && inq.back ().val <= ans[i].val)

inq.pop_back ();

inq.push_back (ans[i]);

while (!deq.empty () && deq.back ().val >= ans[i].val)

deq.pop_back ();

deq.push_back (ans[i]);

}

inq_len = deq_len = 0;

out_inq[inq_len++] = inq.front ();

out_deq[deq_len++] = deq.front ();

for (int i = k + 1; i <= n; i++)

{

if (inq.front ().id + k == ans[i].id)

inq.pop_front ();

while (!inq.empty () && inq.back ().val < ans[i].val)

inq.pop_back ();

inq.push_back (ans[i]);

out_inq[inq_len++] = inq.front ();

if (deq.front ().id + k == ans[i].id)

deq.pop_front ();

while (!deq.empty () && deq.back ().val >= ans[i].val)

deq.pop_back ();

deq.push_back (ans[i]);

out_deq[deq_len++] = deq.front ();

}

for (int i = 0; i < deq_len; i++)

{

if (i == 0)

printf ("%d", out_deq[i].val);

else

printf (" %d", out_deq[i].val);

}

puts ("");

for (int i = 0; i < inq_len; i++)

{

if (i == 0)

printf ("%d", out_inq[i].val);

else

printf (" %d", out_inq[i].val);

}

puts ("");

}

return 0;

}

poj2785

poj2891

超客的水墨烟雨

poj2823

分类目录

标签云

书签

近期评论

2024年4月
一	二	三	四	五	六	日
« 6月
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