Поиск количества способов, с помощью которых можно получить равную сумму?

Question

Итак, я пытаюсь решить this вопрос:

У вас есть массив а [1], а [2], ..., а [п], состоящее из п целых чисел. Подсчитайте количество способов разбиения всех элементов массива на три смежные части, чтобы сумма элементов в каждой части была одинаковой.

Ввод Первая строка содержит целое число n (1 ≤ n ≤ 5 · 10^5), отображающее количество чисел в массиве. Вторая строка содержит n целых чисел a [1], a [2], ..., a [n] (| a [i] | ≤ 10^9) - элементы массива a.

Выход Распечатайте одно целое число - количество способов разделить массив на три части с одинаковой суммой. Например,

input 
5 
1 2 3 0 3 
output 
2 

Мой подход: взять сумму всех входных чисел. Найдите, если он делится на 3 или нет. Если это не так, прямо выведите 0 и если он делится на 3, нам нужно подсчитать количество способов. Поэтому, что я сделал,

Найдено значения индексов (ind1, ind2, ind3), где я могу найти первый подмассив, который удовлетворяет заданному условию. То есть,

int ind1=0,ind2=0,ind3=0; 
    while (ind1 < n) 
    { 
     p = p + arr[ind1]; 
     if (p != val) 
      ind1++; 
     else if (p == val) 
     { 
      f1 = 1; 
      break; 
     } 
    } 
    ind2 = ind1; 
    ind2++; 
    p = 0; 
    while (ind2 < n) 
    { 
     p = p + arr[ind2]; 
     if (p != val) 
      ind2++; 
     else if (p == val) 
     { 
      f2 = 1; 
      break; 
     } 
    } 
    ind3 = ind2; 
    ind3++; 
    p = 0; 
    while (ind3 < n) 
    { 
     p = p + arr[ind3]; 
     if (p != val) 
      ind3++; 
     else if (p == val) 
     { 
      f3 = 1; 
      //ans++; 
      break; 
     } 
    } 

И после того как я ind1, ind2, ind3 я начинаю проверять на наличие 0-х годов, потому что только благодаря им, мы будем иметь более чем один путь. Тем не менее, я не похоже, чтобы получить правильный ответ через это на, например,

Input: 
9 
0 0 0 0 0 0 0 0 0 

Правильный O/P должно быть 28, но шахта выходит быть 7. Является ли моя логика не так?

Редактировать: Как предложено: val = sum/3; // здесь сумма представляет собой сумму всех чисел для (i = n-1; i> = 0; i--) { k = k + arr [i]; if (k == val) назад [i] = 1; } k = 0; для (i = 0; i < n; i ++) { k = k + arr [i]; if (k == val) forward [i] = 1; } long long int ans = 0; для (я = 0; я < N-2; я ++) { , если (вперед [я] == 1) { для (к = I + 2; K < п; K ++) // г + 2 потому что должно быть по крайней мере один элемент, между которым действуют sum/3 { if (назад [k] == 1) ans ++; } } }

Answer 1

Правильное значение O/P должно быть 28, но мое выходит на 7. Является ли моя логика неправильной?

Да. После запуска кода у Вас есть следующие:

ind1 ind2 ind3 
    | | | 
    0 0 0 0 0 0 0 0 0   (1) 

после начала искать нули вы найдете следующие конфигурации

ind1 ind2  ind3 
    | |   | 
    0 0 0 0 0 0 0 0 0   (2) 
    ind1 ind2   ind3 
    | |    | 
    0 0 0 0 0 0 0 0 0   (3) 
    ind1 ind2    ind3 
    | |     | 
    0 0 0 0 0 0 0 0 0   (4) 
    ind1 ind2      ind3 
    | |      | 
    0 0 0 0 0 0 0 0 0   (5) 
    ind1 ind2       ind3 
    | |        | 
    0 0 0 0 0 0 0 0 0   (6) 
    ind1 ind2        ind3 
    | |         | 
    0 0 0 0 0 0 0 0 0   (7) 

, которые являются 7 конфигураций вы найдете. Но это не то, что вы хотите. Сначала вам нужно всего два индекса, а не 3, ваш ind3 должен всегда указывать на последний элемент. Вам нужно рассчитать 3 суммы - от до в ind1-1, от ind1 к ind2, и от ind2 + 1 к п-1. Таким образом, вам нужно иметь ind1> = 1, ind2> = ind1, ind2 < n-1. Таким образом, допустимые конфигурации:

 ind1 
     | 
     ind2       
     |         
    0 0 0 0 0 0 0 0 0   (1) 

     ind1 ind2 
     | |        
    0 0 0 0 0 0 0 0 0   (2) 
     ind1  ind2 
     |   |        
    0 0 0 0 0 0 0 0 0   (3) 
    ... 
     ind1       ind2 
     |        |        
    0 0 0 0 0 0 0 0 0   (7) 

И тогда вы должны начать перемещение ind1 также

   ind1 
       | 
      ind2       
       |         
    0 0 0 0 0 0 0 0 0   (8) 
    ... 

Таким образом, количество конфигураций вы получаете: 7 + 6 + 5 + ... + 1 = 28

Также обратите внимание на то, что этот алгоритм является O (n^2), который, скорее всего, будет зависеть от того, что n может достигать 10^5. Итак, чтобы пройти весь тест, вы должны использовать другой подход. Что вы можете сделать, так это следующее. Сначала вычислим множества индексов массива A = {i | a [0] + a [1] + .. + a [i-1] = sum/3} и B = {i | a [i + 1] + a [i + 2] + ... + a [n-1] = sum/3}. Вы можете хранить A и B в массивах, которые будут отсортированы. Теперь вам нужно найти число пар (i, j), такое, что i из A и j из B такое, что i < = j. Что вы можете сделать, так это то, что вы для каждого индекса i 'в A для поиска наименьшего j' в B, так что i '< = j' (это вы могли бы с бинарным поиском, который принимает время O (log n)). Таким образом, все все индексы j> = j 'будут решением, поэтому вы добавите их счет к общему счету. Это должно дать правильный ответ. Таким образом, для ввода

9 
0 0 0 0 0 0 0 0 0 

вы бы, что А = {1, 2, 3, 4, 5, 6, 7} и B = {1, 2, 3, 4, 5, 6, 7 } (массив идет от 0 до 8). Для индекса 1 в A вы имеете те индексы {1, 2, 3, 4, 5, 6, 7}, которые удовлетворяют задаче, для 2 в A вы имеете {2, 3, 4, 5, 6, 7} и т. Д. Снова у вас есть 7 + 6 + 5 + 4 + ... + 1, но вместо перечисления всех возможных индексов вы найдете их счет, используя двоичный поиск в O (log n). Таким образом, в целом ваш алгоритм будет O (n log n).

Вот реализация идеи moreON, которая далее расширяет идею бинарного поиска. Вместо перезагрузки двоичного поиска каждой итерации при запуске для ранее найденного индекса, который дает O (п) амортизируется время в общем

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

int n; 
long long sum, k; 
int a[500010]; 

void solve() 
{ 
    scanf("%d", &n); 
    for (int i = 0; i < n; ++i) 
     scanf("%d", a + i); 

    for (int i = 0; i < n; ++i) 
     sum += a[i]; 

    if (sum % 3 != 0) { 
     cout << 0 << endl; 
     return; 
    } 
    k = sum/3; 
    vector<int> forward, backward; 
    sum = 0; 
    for (int i = 0; i < n-2; ++i) { 
     sum += a[i]; 
     if (sum == k) { 
      forward.push_back(i+1); 
     } 
    } 
    sum = 0; 
    for (int i = n - 1; i >= 2; i--) { 
     sum += a[i]; 
     if (sum == k) { 
      backward.push_back(i-1); 
     } 
    } 
    reverse(backward.begin(), backward.end()); 

    int j = 0; 
    int fn = forward.size(); 
    int bn = backward.size(); 
    long long ans = 0; 
    for (int i = 0; i < fn; ++i) { 
     while (j < bn && backward[j] < forward[i]) 
      j++; 
     ans += bn-j; 
    } 
    cout << ans << endl; 
} 

int main() 
{ 
    solve(); 
    return 0; 
} 

Answer 2

Первого, что выскакивает на ум, что вы хотите, чтобы найти две точки разделения, связывавшей массив в субе массивы ровно одну трети общей суммы: то есть, от 0 до p1, p1 - ​​p2, а p2 - n-1. Во-вторых, вы хотите обработать случай, когда элемент делает вашу сумму превышением целевого значения. В-третьих, вы хотите обрабатывать нули в массиве разумно.

Answer 3

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

Затем найдите каждый подмассив, содержащий первый элемент * и имеющий сумму, равную ровно одной трети от общего числа. Назовем эти левые субмарины. Это должно занять вас O (n). Вам нужно будет записать, где все это закончится.

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

Не отдавая ничего, теперь найдите количество комбинаций неперекрывающихся * левого и правого подмассивов. (Потому что ясно, что подмассив между ними также имеет требуемую сумму в 1/3 от общего количества. Если вы делаете эту часть умно, это должно быть O (количество левых подзадач + количество правых подмассивов), это, конечно, , все еще O (n).

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

* Следует отметить, что существует некоторая разница в нескольких деталях на основе того, равна ли сумма пустого подмассива 0 или не определена для этой проблемы. Вам также необходимо тщательно рассмотреть это. (Исходя из этого примера, я бы сказал, что сумма пустого подмассива не определена, что означает, что для неперекрывающегося слоя также требуется, чтобы длина не была равна 0 зазор)