170 похожих чатов

Всем привет, есть такое задние: Suppose there are n houses on

a street, n is an odd integer. The location of each house is described by its address h_i, which is a nonnegative integer. Several houses can have the same address.
Local authorities want to build a well on this street. Find the address w of the best position for the well, i. e. the address that minimizes the sum |w - h_1| + ⋯ + |w - h_n|
Input
1) Quantity n of the houses, an odd positive integer.
2) Four positive integers S, A, B, M. Using numbers S, A, B, M, the following pseudocode will generate the sequence of numbers.
X[0] = S
for i = 1 to n-1:
X[i] = (A * X[i-1] + B) mod M

Вопрос: Как сделать этот алгоритм со сложностью O(n)?

Вот мое решение с О(n^2):
int min;
int w;
for(int i = 0; i < x.size(); i++)
{
int temp = 0;
for(int j = 0; j < x.size(); j++)
temp += x[i] - x[j];

if(i == 0 || abs(min) > abs(temp))
{
min = temp;
w = x[i];
}
}

1 ответов

8 просмотров

https://t.me/joinchat/BYlFbEHb2qH6V1-rpTX0pA

Похожие вопросы

Обсуждают сегодня

Господа, а что сейчас вообще с рынком труда на делфи происходит? Какова ситуация?
Rꙮman Yankꙮvsky
29
А вообще, что может смущать в самой Julia - бы сказал, что нет единого стандартного подхода по многим моментам, поэтому многое выглядит как "хаки" и произвол. Короче говоря, с...
Viktor G.
2
30500 за редактор? )
Владимир
47
а через ESC-код ?
Alexey Kulakov
29
Гайс, вопрос для разносторонее развитых: читаю стрим с юарта, нада выделять с него фреймы с определенной структурой, если ли чо готовое, или долбаться с ринг буффером? нада у...
Vitaly
9
Чёт не понял, я ж правильной функцией воспользовался чтобы вывести отладочную информацию? но что-то она не ловится
notme
18
У меня есть функция где происходит это: write_bit(buffer, 1); write_bit(buffer, 0); write_bit(buffer, 1); write_bit(buffer, 1); write_bit(buffer, 1); w...
~
14
Добрый день! Скажите пожалуйста, а какие программы вы бы рекомендовали написать для того, чтобы научиться управлять памятью? Можно написать динамический массив, можно связный ...
Филипп
7
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
длина пакета фиксированная, или меняется?
Okhsunrog
7
Карта сайта