Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » MEDIAN
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
дана последовательность из N чисел a1,a2, ..., an и число M
Надо найти количество подпоследовательностей в которых медиана равна числу M
Пояснения:
Подпоследовательность - это a(i),a(i+1), ... a(i+k) (непрерывно идущие подряд числа из массива A(n))
Медиана - это число, которая будет находиться в середине последовательности после ее сортировки. Например, A={5,1,3}, медиана будет равна 3
Ограничения: 1<=N<=100000, 1<=M<=N
Пожалуйста, решите эту задачу!
Ссылку на условие пожалуйста!
А чему равна медиана, когда количество чисел четное? Среднему арифметическому двух центральных?
длина подпоследовательности всегда нечетная
переберем все длины подпоследовательностей K и для каждой посчитаем ответ деревом отрезков как для k-й порядковой (но только такой, чтобы в ней содержался элемент множ-во А, равный М).
переберем все длины подпоследовательностей K и для каждой посчитаем ответ деревом отрезков как для k-й порядковой (но только такой, чтобы в ней содержался элемент множ-во А, равный М).
Не самый лучший вариант!
А можно всё таки ссылку на условие? Или автор темы взял из головы задачу??
Consider a sequence A of integers, containing N integers between 1 and N. Each integer appears exactly once in the sequence.
A subsequence of A is a sequence obtained by removing some (possibly none) numbers from the beginning of A, and then from the end of A.
Calculate how many different subsequences of A of odd length have their median equal to B. The median of a sequence is the element in the middle of the sequence after it is sorted. For example, the median of the sequence {5, 1, 3} is 3.
Input
The first line contains two integers, N (1 ? N ? 100 000) and B (1 ? B ? N).
The second line contains N integers separated by spaces, the elements of sequence A.
Output
Output the number of subsequences of A whose median is B.
Sample test data
input
5 4
1 2 3 4 5
output
2
input
6 3
1 2 4 5 6 3
output
1
input
7 4
5 7 2 4 3 1 6
output
4
In the fourth example, the four subsequences of A with median 4 are {4}, {7, 2, 4}, {5, 7, 2, 4, 3} and
{5, 7, 2, 4, 3, 1, 6}.
Вот теперь спасибо,эту задачу я уже решал..
Решение такое,найдём где наша медиана в массиве (она там одна,все числа различны).
Теперь пробежим от неё вправо попутно прибавляя +1 к разности кол-ва больших её чисел - кол-во меньших её чисел.
Теперь начнём бежать так же влево,и попутно зная разность кол-ва больших и меньших её чисел,можем узнать сколько краёв справа медианы даст нам такой отрезок что в нём кол-во больших и кол-во меньших чисел равны!
Получаем суть решения в том,что бы каждый момент знать при фиксированном левом крае,кол-во краёв справа медианы,которые в сумме дают равное кол-во больших и меньших чисел медианы,тем самым это и есть свойство медианы.
Сложность алгоритма и память O(N).
Реализация на Паскале(PASCAL):
var a:array[0..100010]of longint;
r:array[-100010..100010]of longint;
id,k,k2,i,n,md:longint;
ans:int64;
begin
read(n,md);
for i:=1 to n do begin
read(a[i]);
if(a[i]=md)then id:=i;
end;
k:=0; k2:=0;
fillchar(r,sizeof(r),0);
for i:=id to n do begin
if(a[i]>md)then inc(k) else if(a[i]<md)then inc(k2);
inc(r[k-k2]);
end;
ans:=0; k:=0; k2:=0;
for i:=id downto 1 do begin
if(a[i]>md)then inc(k) else if(a[i]<md)then inc(k2);
inc(ans,r[k2-k]);
end;
writeln(ans);
end.ппц)))
все элементы различны!
когда формулируешь задачу, такие "мелочи" надо учитывать, если че.
можно было щас еще вспомнить, что время работы программы неограниченно и память 3тб.
ну вообще, brainail вроде правильно написал решение.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » MEDIAN