ломая перестановку чисел от 1 до n в наборе 2

Question

проблемная ссылка: https://codeforces.com/contest/1295/problem/E

эта проблема утверждает, что существует перестановка чисел от 1 до n, так что каждое число встречается только один раз

например. p = [1,2,3] или [2,1,3] для n = 3.

теперь для каждой перестановки в p существует стоимость c _i для я ^й элемент перестановки р. всякий раз, когда я перемещаю элемент i ^th из одного набора в другой, я должен платить c _i .

Итак, вопрос просит меня разбить перестановку в два устанавливаются в любом положении k, так что 1 <= k <n. В принципе, набор не должен быть пустым. Теперь условие состоит в том, что каждый элемент из set1 = (от 1 до k) должен быть меньше от set2 = (k + 1, n). так что для этого у меня есть две операции, либо я могу переместить элемент из set1 в set2, или наоборот. Выполнение этой операции на i-м элементе wold обошлось мне в сумму. Если либо set1, либо set2 пусто, условие выполняется. </p>

например,

p = [3,1,2] c = [7,1,4].

set1 = [3,1] & set2 = [2]. так что теперь мы можем отправить 2 из набора set2 в set1 с минимальной стоимостью 4.

. Для более подробного примера обратитесь к проблеме. Ссылка выше.

мой подход:

для любого k нам нужно иметь элемент от 1 до k в set1 и остаток в set2.
Итак, давайте начнем с i = 1 и продолжаю двигаться до i = n-1 && в каждой позиции. Я поддерживаю pfx и.
Чтобы вычислить массив pfx для каждого pos = i, если p[i] > i, тогда нам нужно добавить стоимость, потому что мы должны передать элемент до set2, и если оно меньше i, тогда мы должны вычесть, потому что мы хотели это раньше, поэтому у нас это было в нашей общей стоимости. но теперь мы не хотим, чтобы это было в наших затратах, поскольку у нас есть ценность. аналогичным образом я также рассчитал для каждой позиции, если у меня было значение cur или нет.

вот мой код. Он проходит много тестовых случаев, но продолжает терпеть неудачу на 10-м. не могу понять причину.

помогите пожалуйста.

#include <bits/stdc++.h>

#define ll unsigned long long
#define pii pair<int,int>

using namespace std;

int main(void)
{
    ll n , ans, prc3=0;
    cin>>n;
    vector<ll> p(n+1),a(n+1);

    for(ll i=1; i<=n; i++) cin>>p[i];
    for(ll i=1; i<=n; i++) cin>>a[p[i]], prc3 += a[p[i]];

    ll prc1=0, prc2=0;
    ll ans1=INT_MAX, ans2=INT_MAX, ans3=INT_MAX;

    vector<bool> vst(n+1,false);

    for(ll i=1; i<n; i++)
    {
        if(p[i]>i)
        {
            prc1 += a[p[i]];
        }
        else if(p[i]<i)
        {
            prc1 -= a[p[i]];
        }

        if(vst[i])
        {
            prc1 -= a[i];
        }

        vst[p[i]] = true;

        if(!vst[i])
        {
            prc1 += a[i];
        }

        ans1 = min(ans1,prc1);

        prc2 += a[p[i]];

        ans2 = min(ans2,prc2);

        prc3 -= a[p[i]];

        ans3 = min(ans3,prc3);


    }

    ans = min(ans1,ans2);
    ans = min(ans,ans3);

    cout << ans << endl;

    return 0;

}

Answer 1

Я не уверен, что именно ваш код пытается сделать в точности, но после того, как я сам решил этот вопрос и, наконец, прочитал редакционную статью , мне кажется, что для достижения решения в рамках ограничений требуется дерево структура данных.

Как я понимаю, мы сохраняем переменную k, которая представляет наибольшее число в левой части. Мы начинаем k с 1 и повторяем до n. В то же время мы сохраняем дерево, в котором каждый ключ i указывает на стоимость создания текущего k раздела, начиная с позиции i.

Когда мы увеличиваем k, все i s, которые являются начальными позициями раздела, большими или равными позиции k в начальном списке, не нуждаются в перемещении этого элемента, поэтому мы обновляем все эти i s, вычитая A[p[k]] из каждого один раз в O(log n) времени, используя дерево; и обновите все i, которые указывают на начальные позиции секций, меньшие k, добавив стоимость каждого перехода. Мы берем минимальные затраты на каждую итерацию.

Насколько я знаю, для обновления сегмента за O(log n) время потребуется древовидная структура данных.