Tag-单调队列

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-03-12 09:15:43 |  0 Comments  |  单调队列

POJ2823 Sliding Window 单调队列维护

题解

经典的单调队列维护。

单调队列可以在O(n)的时间内完成当前查找区间的最大值最小值的维护。

具体实现:

使用双端队列方便元素进出。元素保存的不是数而是数的位置,因为此题涉及到不在区间内的元素的删除,所以我们应该保存书的位置。

两个单调队列都要在遍历时,都要弹出当前不在查找区间内的元素。我们可以保证,如果要弹出,那么这个元素一定在队列的最开头。

第一个单调队列维护区间最小值,如果当前位置上的数比单调队列中的最后一个元素位置上的数大,则删除单调队列末尾位置的元素,一直到队列为空或者队列末尾元素位置的数比当前位置的数小,然后将当前位置编号加入队列。

第二个单调队列维护区间最大值,类比第一个单调队列。

记得循环的时候就保存答案。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e6+5;
int n,k;
int a[maxn];
dequeq1;
dequeq2;
int ans1[maxn];
int ans2[maxn];
int main(){
    n = get_num();
    k = get_num();
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
    }
    for(int i = 1;i
 2016-12-14 21:01:02 |  1 Comments  |  机智题 单调队列

NOIP[2016Day2T2]蚯蚓

NOIP[2016Day2T2]蚯蚓

题目描述

本题中,我们将用符号[c]表示对c向下取整,例如:[3.0」= [3.1」=[3.9」=3。
蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为a_i(i=1,2,...,n),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。
每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为[px]和x-[px]的蚯蚓。特殊地,如果这两个数的其中一个等于0,则这个长度为0的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(是一个非负整常数)。
蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要m秒才能到来...... (m为非负整数)
蛐蛐国王希望知道这m秒内的战况。具体来说,他希望知道:
m秒内,每一秒被切断的蚯蚓被切断前的长度(有m个数)
m秒后,所有蚯蚓的长度(有n+m个数)。
蛐蛐国王当然知道怎么做啦!但是他想考考你......

输入格式

第一行包含六个整数n,m,q,u,v,t,其中:n,m,q的意义见【问题描述】;u,v,t均为正整数;你需要自己计算p=u/v(保证0<u<v)t是输出参数,其含义将会在【输出格式】中解释。
第二行包含n个非负整数,为ai,a2,...,an,即初始时n只蚯蚓的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。
保证1<=n<=105 ,0<m<7*106 ,0<u<v<109 ,0<=q<=200 ,1<t<71 ,0<ai<108。

输出格式

第一行输出[m/t]个整数,按时间顺序,依次输出第t秒,第2t秒,第3t秒……被切断蚯蚓(在被切断前)的长度。
第二行输出[(n+m)/t]个整数,输出m秒后蚯蚓的长度;需要按从大到小的顺序,依次输出排名第t,第2t,第3t……的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。即使某一行没有任何数需要 输出,你也应输出一个空行。
请阅读样例来更好地理解这个格式。

样例输入

3 7 1 1 3
Title - Artist
0:00