两道单调队列题目 (初识单调队列)

发表于 更新于 分类于 ， ， 本文字数： 4.8k 阅读时长 ≈ 9 分钟

尺取法、单调队列、滑动窗口一直傻傻分不清。以前觉得尺取法就是滑动窗口，现在又觉得单调队列和滑动窗口是一回事。

算法的美妙之处就在于当你明了一个算法时，会发自内心惊叹它的美。我于树状数组如此，学习单调队列后亦如此。

关于单调队列的用法主要看了下单调队列及其应用中的内容， 以下引用一些内容。

单调队列及其应用

单调队列，望文生义，就是指队列中的元素是单调的。如：{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。

单调队列的出现可以简化问题，队首元素便是最大（小）值，这样，选取最大（小）值的复杂度便为o（1），由于队列的性质，每个元素入队一次，出队一次，维护队列的复杂度均摊下来便是o（1）。

如何维护单调队列呢，以单调递增序列为例：

1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。

2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止

要特别注意头指针和尾指针的应用。

1. Non-negative Partial Sums(Southwestern European Regional Programming Contest 2011 - Gym 101561G - Uva 12393)

Problem

Description

You are given a sequence of n numbers a0, . . . , an−1. A cyclic shift by k positions (0 ≤ k ≤ n − 1) results
in the following sequence: ak, ak+1, . . . , an−1, a0, a1, . . . , ak−1. How many of the n cyclic shifts satisfy the
condition that the sum of the first i numbers is greater than or equal to zero for all i with 1 ≤ i ≤ n?

Input

Each test case consists of two lines. The first contains the number n $(1 ≤ n ≤ 10^6)$, the number of
integers in the sequence. The second contains n integers a0, . . . , an−1 (−1000 ≤ ai ≤ 1000) representing the
sequence of numbers. The input will finish with a line containing 0.

Output

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the
condition stated above.

Sample Input

3
2 2 1
3
-1 1 1
1
-1
0

Sample Output

3
2
0

Solution

Todo

一个数列，依次将最后一个数移到最前边，问有多少种情况其前缀和均大于等于 0。

Idea

队友给我讲完题意后第一反应就是将数列再复制一倍，如 -1 1 1 变为 -1 1 1 -1 1 1。之后 = w=，就没思路啦。之后接触啦单调队列，发现实在是太神奇啦 QAQ。

Code

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
#define MAXN 1000010
typedef long long LL;

using namespace std;

int n;

int a[MAXN], sum[MAXN<<1];
int que[MAXN<<1];

int main()
{
    while(scanf("%d", &n) && n)
    {
        scanf("%d", &a[0]);
        sum[0] = a[0];
        for(int i=1; i<n; i++)
        {
            scanf("%d", a+i);
            sum[i] = sum[i-1] + a[i];
        }

        for(int i=n; i<(n<<1); i++)
            sum[i] = sum[i-1] + a[i-n];

        int l = 0, r = 0;
        int ans = 0;

        for(int i=0; i<(n<<1); i++)
        {
            // l<r表示队列非空
            while(l<r && sum[i] < sum[que[r-1]])	//入队操作，参照引用中的1
                r--;
            que[r++] = i;

            if(i>=n && sum[que[l]] - sum[i-n] >= 0)
                ans++;
            while(l<r && que[l] <= i-n+1)	//出队操作，将超出区间的出队
                l++;
        }

        printf("%d\n", ans);
    }
    return 0;
}

2. Miraculous Drug(Southeastern European Regional Programming Contest 2012, Gym 101472G)

Problem

Description

Input File: G.IN
Output File: standard output
Program Source File: G.C, G.CPP, G.JAVA

Joe is an enthusiast biomedical researcher. He is very close to discover the cure for a terrible
disease. In order to prepare the miraculous drug he needs to buy a special enzyme, that is quite
expensive and unfortunately loses its properties after a fixed period of time. Now Joe is in the
clinical trial phase. He needs a drug available at each hour. Thus he has to prepare exactly the
same quantity of drug every hour. The price of the enzyme might vary from hour to hour. The cost
of the enzyme on hour i is ci. The life time of the enzyme is h hours. Given the prices for the
next n hours, Joe has to find out the optimal cost to purchase enzymes such that the drug is
available in each of the n hours. If the price is the same Joe prefers to buy fresh enzymes, not to
stock them. We assume an unlimited quantity of enzymes is available each hour. Can you help
Joe?
The program input is from a text file. The file contains several data sets. A data set starts with the
number n (n<10000) of hours. Follows h (h<10000) the number of hours of the enzyme life
time, b the starting point, e the ending point of the printing interval (1≤b,e≤n), and the enzyme
costs ci (ci<10000), i=1..n. The program prints for each hour in the interval [b,e] the
number of enzymes Joe decides to buy.
White spaces can occur freely in the input. The input data are correct and terminate with an end
of file. For each set of data the program prints the result to the standard output from the beginning
of a line. An input/output sample is in the table below. There are two data sets. For the first one
n=6, h=3, b=1, e=6, and the costs are 5 4 4 3 5 6. The result consists of the numbers of
enzymes bought every hour, printed from the beginning of the line, separated with tabs.

Sample input

6 3 1 6
5 4 4 3 5 6
3 3 2 3

Sample output

1 1 1 3 0 0
1 1

Solution

Idea

昨天刚看的单调队列，没想到今天就有一个题。

看到的第一眼就想用单调队列来做。

细菌存活的寿命即为滑动窗口的长度，队列存当前可买的细菌为第几天，队首存价格最低时为第几天，递增队列。现在感觉单调队列蛮灵活的，出队入队写的位置根据题目来确定。

Code

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
#define MAXN 10010
typedef long long LL;

using namespace std;

int ans[MAXN], que[MAXN], c[MAXN], res[MAXN];
int b, e, n, h;

int main()
{
    freopen("G.IN", "r", stdin);
    while(scanf("%d%d%d%d", &n, &h, &b, &e) == 4)
    {
        memset(res, 0, sizeof(res));
        for(int i=1; i<=n; i++)
            scanf("%d", c+i);
        int l=0, r=0;
        int stock=0;
        for(int i=1; i<=n; i++)
        {
            while(l<r && i - que[l] >= h)		//出队操作，到今天过期的细菌不可再买，故出队
                l++;
            while(l<r && c[i] <= c[que[r-1]])	//入队操作
                r--;
            que[r++] = i;



            if(stock == 0)
            {
                ans[i] = que[l];	//第ans[i]天买第que[l]天的
                stock=1;
            }

            stock--;
        }

        for(int i=1; i<=n; i++)
            res[ans[i]]++;
        for(int i=b; i<=e; i++)
            printf("%d%c", res[i], " \n"[i==e]);
    }
    return 0;
}

Node

初识单调队列的两道题，感觉应该蛮经典的。很开心第二天可以自己码出答案并 1A。