Реши на c++

Кратко о задаче

• Есть n станций с позицией a_i и количеством Лаббу p_i.
• Нужно выбрать станцию j, на которую перевезти всю Лаббу, чтобы сумма затрат sum_i p_i * |a_i - a_j| была минимальна.
• Если таких станций несколько, выбрать с наименьшим индексом.

Ключевая идея

• Минимум функции суммарной доставки достигается на весовом медиане набора точек a_i с весами p_i.
• При ограничении выбора на существующие станции j оптимальным будет первая станция по порядку с накопленным весом не менее половины общего веса.
• То есть найти минимальный j такой, что суммарная масса до j включительно достигает (total_p + 1) / 2.

Алгоритм

1. прочитать n, массив a[1..n], и массив p[1..n].
2. посчитать total = sum p_i.
3. определить порог half = (total + 1) / 2.
4. пройти по i от 1 до n, накапливая sum_p = sum p_1..p_i; первый i, для которого sum_p >= half, и есть ответ.
5. вывести этот индекс i (1-based).

Сложность: время O(n), память O(1) помимо входных массивов. Тип чисел long long, так как total может быть до около 3e11.

Пример кода (C++):

#include <bits/stdc++.h> using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int n;
if (!(cin >> n)) return 0;

vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];

vector<long long> p(n + 1);
long long total = 0;
for (int i = 1; i <= n; ++i) {
    cin >> p[i];
    total += p[i];
}

long long half = (total + 1) / 2;
long long pref = 0;
int ans = 1;
for (int i = 1; i <= n; ++i) {
    pref += p[i];
    if (pref >= half) {
        ans = i;
        break;
    }
}

cout << ans << "\n";
return 0;

}

Пояснение по выбору индекса

• Если общее количество Лаббу нечетное, порог half равен (total+1)/2, что соответствует медиане.
• Если четное, выбирается первая станция, у которой накопленный вес достигает или превышает total/2, что обеспечивает минимизацию целевой функции и, при равенстве, гарантирует минимальный индекс благодаря порядку обхода.

Если хочешь, могу привести пример с конкретными числами и показать расчёт вручную.