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

Учитывая массив arr[] , задача состоит в том, чтобы напечатать индексы, которые имеют наибольшую вероятность хранения всей суммы массива после выполнения данных операций:

• Выберите любые два элемента, скажем, arr[i] и arr[j] , сохраните их сумму в переменной K
• Присвойте K индексу max(arr[i], arr[j]) и присвойте 0 индексу min(arr[i], arr[j])

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

Примеры:

Input: arr[] = {2, 1, 4}
Output: {2}
Explanation: Choosing of elements can be done in the following ways:

Way 1:

• Choose elements at indices {0, 1}, so arr[] = {3, 0, 4}
• Choose elements at indices {0, 2}, so arr[] = {0, 0, 7}

Way 2:

• Choose elements at indices {0, 2}, so arr[] = {0, 1, 6}
• Choose elements at indices {1, 2}, so arr[] = {0, 0, 7}

Way 3:

• Choose elements at indices {1, 2}, so arr[] = {2, 0, 5}
• Choose elements at indices {0, 2}, so arr[] = {0, 0, 7}

In this case, output = {2}, index 0 and index 1 has zero possibility of holding the sum, so it is excluded.

Input: arr[] = {1, 2, 4, 3}
Output: {1, 2, 3}

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

1. Возьмите вектор пары, скажем, v , сохраните все элементы вместе с соответствующими индексами в паре, также возьмите переменную, скажем, сумму , которая будет хранить сумму всего массива.
2. Отсортируйте вектор в порядке возрастания и возьмите счетчик, скажем , c, инициализируйте с 1 , потому что у одного индекса всегда будет возможность хранить сумму массива.
3. Переберите вектор от второго последнего элемента и проверьте, больше ли сумма до второго последнего элемента , чем сумма до конца (т.е. сумма массива), если она больше , затем увеличьте счетчик, что означает, что он имеет возможность удержания суммы, иначе разорвите цикл, поскольку это недопустимый индекс.
4. Возьмите вектор, скажем, ans , чтобы сохранить действительные индексы и сохранить индексы, повторяя от конца до счетчика, затем отсортируйте вектор ans и распечатайте его.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(NlogN)
Вспомогательное пространство : O(N)