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

Question

Всем привет, есть такое задние: 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];
}
}

#c++ #embedded #programming #russian

0

25.03.2021

1 ответов

8 просмотров

Aidar Fattakhov · Accepted Answer

Aidar Fattakhov

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

0

25.03.2021

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

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

1 ответов

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