Сложность понимания чьего-либо исходного кода для решения проблемы IOI - PullRequest
Новая
       55

Сложность понимания чьего-либо исходного кода для решения проблемы IOI

1 голос
/ 10 июля 2020

Вот ссылка на проблему: https://ioi2019.az/source/Tasks/Day1/Shoes/NGA.pdf

Вот краткое объяснение проблемных государственных деятелей t:

Вы дается целое число n в диапазоне 1≤n≤1e5 , которое будет представлять количество положительных целых чисел внутри массива, а также количество отрицательных целых чисел в массив (таким образом, общий размер массива будет 2n ).

Задача состоит в том, чтобы вы нашли минимальное количество свопов, необходимых в массиве, чтобы отрицательное значение числа и абсолютные значения этого отрицательного числа соседствуют друг с другом ( так, что -x находится справа от x)

Пример:

n = 2;

массив inputed = {2, 1, -1, -2}

Минимальное количество операций будет четыре:

2,1, -1, -2: 0 свопов

2, -1,1, -2: 1 своп (замена 1 и -1)

2, -1, -2,1: 2 своп (замена 1 и - 2)

2, -2, -1,1: 3 перестановки (замена -1 и -2)

-2,2, -1,1: 4 обмена (меняем местами 2 и -2)

Окончательный ответ будет четыре.

Другой пример:

массив inputed = {-2, 2, 2, -2, -2, 2}

Минимальный своп равен единице. Потому что мы можем просто поменять местами элементы с индексами 2 и 3.

Окончательный массив: {-2,2, -2,2, -2,2}

Задавая этот вопрос, я получил неправильный ответ и решил посмотреть чей-то исходный код на git хабе.

Вот исходный код: 

#include "shoes.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;

struct bit{
    int tree[MAXN];
    void add(int x, int v){
        for(int i=x; i<MAXN; i+=i&-i) tree[i] += v;
    }
    int query(int x){
        int ret = 0;
        for(int i=x; i; i-=i&-i) ret += tree[i];
        return ret;
    }
}bit;


lint count_swaps(vector<int> s) {
    int n = sz(s) / 2;
    lint ret = 0;
    vector<pi> v;
    vector<pi> ord[MAXN];
    for(int i=0; i<sz(s); i++){
        ord[abs(s[i])].emplace_back(s[i], i);
    }
    for(int i=1; i<=n; i++){
        sort(ord[i].begin(), ord[i].end());
        for(int j=0; j<sz(ord[i])/2; j++){
            int l = ord[i][j].second;
            int r = ord[i][j + sz(ord[i])/2].second; //confusion starts here all the way to the buttom
            if(l > r){
                swap(l, r);
                ret++;
            }
            v.emplace_back(l + 1, r + 1);
        }
    }
    for(int i=1; i<=2*n; i++) bit.add(i, 1);
    sort(v.begin(), v.end());
    for(auto &i : v){
        ret += bit.query(i.second - 1) - bit.query(i.first);
        bit.add(i.first, -1);
        bit.add(i.second, -1);
    }
    return ret;
}

Однако я Не думаю, что я слишком хорошо понимаю этот код.

Я понимаю, что такое функции add и query в BIT. Я просто не понимаю, где я прокомментировал код до конца. Я не понимаю, что он делает и какова его цель.

Может ли кто-нибудь пройти через то, что делает этот код? Или дайте какие-либо предложения, как правильно и эффективно подойти к этой проблеме (даже, возможно, ваши решения?). Спасибо.

1 Ответ

1 голос
/ 11 июля 2020 
int r = ord[i][j + sz(ord[i])/2].second;

Мы отсортировали кортежи одного размера обуви в векторе <size, idx>, что означает, что все негативы этого размера занимают первую половину ord[i], а все положительные - во второй. половина. 

if (l > r){
  swap(l, r);
  ret++;
}

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

v.emplace_back(l + 1, r + 1);

вставьте в v наш интервал для соответствующей пары обуви размером i. 

for(int i=1; i<=2*n; i++) bit.add(i, 1);
sort(v.begin(), v.end());

Добавьте значение 1 в нашем дереве суммы сегментов для каждого местоположения индекса обуви. Отсортируйте интервалы между ботинками. 

for(auto &i : v){
  ret += bit.query(i.second - 1) - bit.query(i.first);

Для каждой пары обуви в v необходимое количество замен - это количество обуви, оставшееся между ними, выраженное в сумме сегментов. 

bit.add(i.first, -1);
bit.add(i.second, -1);

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

...