2248. Суперминимум
Дано n чисел. Для
каждых k подряд идущих чисел найдите
минимальное среди них.
Вход. В первой строке даны числа n и k (1 ≤ n ≤ 106, 1 ≤ k ≤ n). Во второй строке записано n
целых чисел в диапазоне от -32768 до 32767.
Выход. Для каждых k подряд идущих чисел выведите
минимальное из них.
|
Пример
входа |
Пример
выхода |
11 3
8 764 1 3 85
2 4 5 77 1 5 |
1 1 1 2 2 2 4 1 1 |
РЕШЕНИЕ
очередь
Анализ алгоритма
Реализуем
очередь с поддержкой минимума. Занесем в очередь первые k элементов. Выведем минимум в очереди. Далее извлечем один элемент
из очереди и занесем в нее следующий. Таким образом очередь будет содержать
вторые k элементов. Снова выводим
минимум. Повторяя процесс извлечения и вставки в очередь, мы переберем все
наборы из k подряд идущих чисел. Для
каждого такого набора выводим минимум.
Пример
Рассмотрим
процесс вычисления минимумов для заданного примера.
Реализация алгоритма
Реализуем класс
очередь, поддерживающий минимум в очереди.
class Deque
{
private:
deque<int>
q, min;
public:
void pop(void)
{
if
(!q.empty())
{
if
(q.front() == min.front()) min.pop_front();
q.pop_front();
}
}
int getMin(void)
{
return
(min.empty()) ? 0 : min.front();
}
void push(int x)
{
q.push_back(x);
while(!min.empty()
&& x < min.back()) min.pop_back();
min.push_back(x);
}
};
Основная часть программы. Читаем входные данные. Объявляем
очередь d.
scanf("%d %d",&n,&k);
Deque d;
Заносим первые k
элементов в очередь.
for(i = 1; i <= k; i++)
{
scanf("%d",&x);
d.push(x);
}
Выводим минимум текущих k
элементов. Читаем следующее число x.
Извлекаем число из очереди и заносим в нее x.
Таким образом очередь содержит следующие k
последовательных элементов. Повторяем цикл пока очередь не будет содержать
последние k элементов из n заданных чисел.
for(; i <= n; i++)
{
printf("%d
",d.getMin());
scanf("%d",&x);
d.pop();
d.push(x);
}
Выводим минимум последних k
элементов.
printf("%d\n",d.getMin());
Реализация алгоритма – класс очередь, моделирование
очередей массивами
#include <stdio.h>
int n, k, i, x;
class Deque
{
private:
int *value, *mn;
int Bvalue,
Evalue, Bmn, Emn;
public:
Deque(int n =
150010)
{
value = new
int[n];
mn = new int[n];
Bvalue = Evalue = Bmn = Emn = 0;
}
~Deque()
{
delete[]
value;
delete[]
mn;
}
void pop(void)
{
if (Bvalue
!= Evalue)
{
if
(value[Bvalue] == mn[Bmn]) Bmn++;
Bvalue++;
}
}
int getMin(void)
{
return (Bmn
!= Emn) ? mn[Bmn] : 0;
}
void push(int x)
{
value[Evalue++] = x;
while((Bmn
!= Emn) && (x < mn[Emn-1])) Emn--;
mn[Emn++] = x;
}
};
int main(void)
{
scanf("%d
%d",&n,&k);
Deque d(n);
for(i = 1; i
<= k; i++)
{
scanf("%d",&x);
d.push(x);
}
for(; i <=
n; i++)
{
printf("%d
",d.getMin());
scanf("%d",&x);
d.pop();
d.push(x);
}
printf("%d\n",d.getMin());
return 0;
}
Реализация
алгоритма – массивы
#include <cstdio>
#define MAX 150010
int n, k, i, v;
int q[MAX], m[MAX], qh, qt, mh, mt;
int main(void)
{
scanf("%d
%d",&n,&k);
qh = qt = mh = mt = 0;
for(i = 1; i
<= k; i++)
{
scanf("%d",&v);
q[qt++] = v;
while((mh
< mt) && (v < m[mt-1])) mt--;
m[mt++] = v;
}
printf("%d",m[mh]);
for(; i <=
n; i++)
{
scanf("%d",&v);
if (q[qh]
== m[mh]) mh++; qh++;
q[qt++] = v;
while((mh
< mt) && (v < m[mt-1])) mt--;
m[mt++] = v;
printf("
%d",m[mh]);
}
printf("\n");
return 0;
}