Вопрос:

Логика, используемая за Манипуляцией Массивом HackerRank

c++ arrays

9092 просмотра

5 ответа

689 Репутация автора

Я не могу понять логику решения этой проблемы Hackerrank, https://www.hackerrank.com/challenges/crush/problem

В разделе для обсуждения многие также опубликовали свои решения, но я не могу понять, почему эта логика работает.

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

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    long int N,K,p,q,sum,i,j,max=0,x=0;

    cin>>N>>K;
    long int *a=new long int[N+1]();

    for(i=0;i<K;i++)
    {
        cin>>p>>q>>sum;
        a[p]+=sum;
        if((q+1)<=N) a[q+1]-=sum;
    }

    for(i=1;i<=N;i++)
    {
       x=x+a[i];
       if(max<x) max=x;

    }

    cout<<max;
    return 0;
}

Может кто-нибудь объяснить, пожалуйста, логику того же? Большое спасибо за вашу помощь.

Автор: Vivek kumar Источник Размещён: 09.01.2018 06:00

Ответы (5)


29 плюса

27527 Репутация автора

Решение

В основном мы храним приращение начального и одного последнего элемента в диапазоне. Для a b kнас будет увеличиваться +kдля всех элементов в индексе , [a,b]а затем следующие элементы не будут увеличены. Поэтому мы вычитаем это, потому что по сравнению с предыдущим приращением все элементы справа от диапазона будут меньше -k. Мы в основном храним все конечные значения с помощью этого увеличения / уменьшения.

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

Изначально массив будет 0 0 0 0 0.

После первой операции 1 3 3изначально должны быть элементы массива, 3 3 3 0 0но мы храним это так

3 0 0 -3 0

Имея в виду

First element is 3 greater than 0.
Second  ->       0 greater than index 1 element.
Third   ->       0 greater than index 2 element
Fourth  ->      -3 greater than index 3 element.
fifth   ->       0 greater than index 4 element.

После второй операции 2 4 4первоначально массив будет, 3 7 7 4 0но мы храним его так 3 4 0 -3 -4. Точно так же, как я описал подробно, имейте в виду, что, думая так, вы увидите, что мы не теряем информацию. Мы просто храним это по-другому.

Конечные значения будут

0+(3) 0+3+(4) 0+3+4+(0) 0+3+4+0+(-3) 0+3+4+0-3+(-4)

3  7    7       4           0  matches with what we got earlier.

Обратите внимание, как мы рассчитываем каждый элемент. Просто добавьте предыдущий элемент со значением, на которое текущий элемент больше.


Обратите внимание, что это решение работает, потому что оно запрашивается только один раз. если это запрашивается mраз также, то этот вариант не работает. Тогда вам придется копать глубже, используя segment treeили binary indexed tree.

Автор: coderredoc Размещён: 09.01.2018 06:09

3 плюса

1998 Репутация автора

Я попытаюсь объяснить мое понимание этого:
каждая строка ввода в основном описывает последовательность, и вас просят найти максимальное значение суммы этих последовательностей.
Например, если Nзадано как 5:
строка 2 4 13описывает последовательность, [0, 13, 13, 13, 0]
строка 3 5 11описывает последовательность [0, 0, 11, 11, 11].
Если это единственные строки, мы получаем результирующую последовательность из поточечной суммы двух, то есть [0, 13, 24, 24, 11].

Теперь мы можем описать приведенные выше последовательности еще раз с помощью разностных последовательностей, то есть с индексом iмы сохраним разницу между элементом с индексом iи элементом с индексом i-1, и мы можем получить исходную последовательность по текущей сумме разности. последовательность.

В случае вышеупомянутых последовательностей разностные последовательности представляют собой:
[0, 13, 0, 0, -13]для последовательности, описанной с помощью, 2 3 13
[0, 0, 11, 0, 0]для последовательности, описанной с помощью, 3 5 11
[0, 13, 11, 0, -13для суммы последовательностей.

Одним важным свойством разностной последовательности является сумма сумм последовательностей, являющаяся суммой разностных последовательностей .

Таким образом, решение для каждой строки состоит в суммировании разностных последовательностей (что требует только до 2 операций из-за природы последовательностей), а затем для нахождения максимума, который требуется для промежуточного итога разностной последовательности, таким образом элементы последовательности и содержит максимальное значение этой промежуточной суммы.

Хотя в приведенном мной примере всего две строки, эта же идея работает для любого количества строк.

Я надеюсь, что это дает хорошую интуицию относительно идеи решения.

Автор: M. Aroosi Размещён: 09.01.2018 06:23

3 плюса

58 Репутация автора

Эти два места помогли мне понять этот алгоритм более четко. Prefix_sum_array_and_difference_array
Переполнение стека

Если вам нужно простое и прямое объяснение: Initial, массив равен 0 0 0 0 0, cpp after the first operation, 1 2 100 it will become seq1: 100 100 0 0 0 and after second 2 5 100 seq2: 0 100 100 100 100 and after 3 4 100 seq2: 0 0 100 100 0 но когда мы применяем массив разностей на каждом шаге, мы получим

cpp diff seq of seq1: 100 0 -100 0 0 diff seq of seq2: 0 100 0 0 0 -100 diff seq of seq3: 0 0 100 0 -100

Одним важным свойством разностной последовательности является сумма сумм последовательностей, являющаяся суммой разностных последовательностей.

это даст нам, cpp 100 100 0 0 -100 -100(for clarity purpose only) или вы можете добавить все последовательности как cpp seq1+seq2+seq3 = 100 200 200 200 100 и затем найти разницу seq или массив разностей 100 100 0 0 -100, а затем найти массив префиксов.

Почему мы игнорируем первые 100 ??? Прочтите первую статью о массиве разностей и массиве префиксов !!!!

и после этого префикс sum cpp 100 200 200 200 100 0 игнорировать последние 0, так как последний рассматриваемый нами индекс предназначен только для ясности.

Итак, оба эти шага находят для нас массив различий :) cpp a[p]+=sum; if((q+1)<=N) a[q+1]-=sum;

Автор: Surendra Meena Размещён: 18.01.2018 10:11

1 плюс

21 Репутация автора

Следующий код работал для меня в C ++. Я взял некоторую помощь онлайн и затем закодировал это.

long arrayManipulation(int n, vector<vector<int>> queries) {
  vector<long> resultVector(n);
  long maxVal=0, x=0, i;

  for(int i = 0; i<n ; i++)
  {
      resultVector[i]=0;
  }

  for(i=0; i<queries.size(); i++)
  {
      resultVector[(queries[i][0])-1] += queries[i][2];

      if((queries[i][1]) <= n)
      {
          resultVector[(queries[i][1])] -= queries[i][2];
      }
  }

  for(i=0; i <n; i++)
  {
      x+=resultVector[i];
      if(x>maxVal)
      {
          maxVal=x;
      }
  }

  return maxVal;
}
Автор: Ankit Sinha Размещён: 19.12.2018 05:50

0 плюса

91 Репутация автора

вместо добавления k ко всем элементам в диапазоне от a до b в массиве, накапливайте массив разностей

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

ex = n = 5, m = 1, a = 2 b = 5 k = 5

    i     0.....1.....2.....3.....4.....5.....6   //take array of size N+2 to avoid index out of bound
  A[i]    0     0     0     0     0     0     0

Добавьте k = 5 к a = 2

A [a] = A [a] + k // начальный индекс, откуда следует добавить элемент k, аналогично a [p] + = sum;

     i    0.....1.....2.....3.....4.....5.....6 
   A[i]   0     0     5     0     0     0     0

Теперь примените алгоритм суммирования префиксов

     i    0.....1.....2.....3.....4.....5.....6 
  A[i]    0     0     5     5     5     5     5

так что вы можете видеть добавление K = 5 ко всему элементу до конца после применения префиксной суммы, но нам не нужно добавлять k до конца. поэтому, чтобы свести на нет этот эффект, мы должны добавить -K также после индекса b + 1, чтобы только из диапазона [a, b] только эффект K был добавлен.

A [b + 1] = A [b] -k //, чтобы удалить эффект ранее добавленного элемента k после b-го индекса (аналогично [q + 1] - = sum;), поэтому добавление -k в начальный индекс массив вместе с + к.

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     0     0     0    -5

Теперь примените префикс sum Array

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     5     5     5     0

Вы можете видеть, что теперь K = 5 добавлено от a = 2 до b = 5, что и ожидалось. Здесь мы обновляем только два индекса для каждого запроса, поэтому сложность будет O (1).

Теперь примените тот же алгоритм на входе

         # 0.....1.....2.....3.....4.....5.....6    //taken array of size N+2 to avoid index out of bound
5 3      # 0     0     0     0     0     0     0
1 2 100  # 0    100    0   -100    0     0     0       
2 5 100  # 0    100   100  -100    0     0   -100
3 4 100  # 0    100   100    0     0  -100   -100

Чтобы вычислить максимальную сумму префикса, накопите массив разностей до to, принимая максимальный накопленный префикс.

После выполнения всех операций теперь применяется префикс sum Array

    i      0.....1.....2.....3.....4.....5.....6 
  A[i]     0     100   200  200   200   100    0

Теперь вы можете обойти этот массив, чтобы найти максимальное значение, равное 200. Обход массива займет O (N) времени, а обновление двух индексов для каждого запроса займет O (1) * количество запросов (м)

общая сложность = O (N) + O (M) = O (N + M)

это означает = (10 ^ 7 + 10 ^ 5), что меньше 10 ^ 8 (в секунду)

Примечание: если вы ищете видеоурок , вы должны проверить его здесь для подробного объяснения.

Автор: Kanahaiya Размещён: 08.04.2019 08:39
Вопросы из категории :
32x32