Поиск индеска елемента начиная с которого можно вернутся к этому же элементу

@Vaderkos · Регистрация: 31.03.2015

Студворк — интернет-сервис помощи студентам

Есть кольцевой односвязный список случайного размера с числами в котором числа идут в в таком виде +a -b +c -d +e -f +g -h (последнее и первое число могут иметь одинаковые знаки)

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

Например.

Lisp
1
2
3
4
5
6
 
-6 -> 4 -> -8 -> 10 
 
4 - 8 = -4 (сумма отрицательна)
 
10 - 6 = 4 -> 4 + 4 = 8 -> 8 - 8 = 0 (ответ 4ый элемент, число: 10, максимальная сумма: 10)

Я придумал небольшой алгоритм, который описываю ниже, но он почему то не всегда срабатывает. Может кто-нибудь знает алгоритм и получше?

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Стартовый кольцевой односвязный список.
[35,  -113,  4,  -1,  128,  -30,  16,  -70,  31,  -1,  50,  -81,  32]
 
1. Группировка чисел парами (положительное отрицательное) и получение списка сумм этих пар c индексами этих чисел
2. Объединение чисел с тем самым знаком
3. Если длинна получившиегося списка больше 2 то повторить от пункта 1
4. Проверка и нахождение максимального числа
 
  [35,  -113,  4,  -1,  128,  -30,  16,  -70,  31,  -1,  50,  -81,  32]
   \_______/   \____/   \_______/   \______/   \_____/   \______/   \/
1)  0: -78     |2: 3     4: 98 |     6: -54     8: 30     10: -31  12: 32
               \_______________/                     
2)  0: -78|    |     2: 101          6: -54|   |8: 30     10: -31| |12: 32 <-  Элементы имеют разные знаки, 
...______/     \___________________________/    \_______________/   \______... можно обьединить последний и первый в пару
1) 12: -46              2:   47                      8: -1
2) Объединение [8: -47, 2: 47];
4) Проверка и нахождение максимального числа
Начинаем со второго элемента
        (4   - 1   = 3    )->
max     (3   + 128 = [131])->
        (131 - 30  = 101  )->
        (101 + 16  = 117  )->
        (117 - 70  = 47   )->
        (47  + 31  = 78   )->
        (78  - 1   = 77   )-> 
        (77  + 50  = 127  )->
        (127 - 81  = 46   )->
        (46  + 32  = 78   )->
        (78  + 35  = 113  )->
        (113 - 113 = 0    )
 
Конечная сумма равна нулю, ответ индекс-элемента: 2, максимальное-число: 131

@TopLayer · 31.03.2017, 14:17

Сообщение от Shamil1

Какие правильные ответы для всех трёх вариантов?

Поиск индеска елемента начиная с которого можно вернутся к этому же элементу

Сообщение от Shamil1

Я вижу в данных, что городе в №13 можно заправить только 491

Нумерация городов с нуля, первое число в паре - заправка

@Shamil1 · 31.03.2017, 14:47

TopLayer,
То есть, фразу:

Сообщение от Vaderkos

1: Количество топлива нужное что бы доехать к данному городу
2: Кличество топлива которое можно заправить в данном городе.

нужно понимать как:
1: Кличество топлива которое можно заправить в данном городе.
2: Количество топлива нужное что бы доехать к следующему городу

@TopLayer · 31.03.2017, 14:54

Shamil1, видимо так, судя по посту 33.

@Shamil1 · 31.03.2017, 15:30

Сообщение от TopLayer

видимо так, судя по посту 33

Тогда решение:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
Tuple<int,long> Solve(TextReader stream)
{
    int n = ReadInt(stream);
    int mini = -1;
    long si = 0, mins = long.MaxValue, maxs = long.MinValue;
    for (int i = 0; i < n; i++)
    {
        int x1 = ReadInt(stream);
        int x2 = ReadInt(stream);
        si += x1 - x2;
        if (si < mins)
        {
            mins = si;
            mini = i;
        }
        else if (si > maxs)
        {
            maxs = si;
        }
    }
    return Tuple.Create((mini + 1) % n, maxs - mins);
}
 
 
int ReadInt(TextReader stream)
{
    int result = 0;
    int c = stream.Read();
    if (c == '\n') c = stream.Read();
    while ('0' <= c && c <= '9')
    {
        result = result * 10 + c - '0';
        c = stream.Read();
    }
    return result;
}
 
void Main()
{
    string input1 = @"6
9 15
7 3
7 14
2 3
4 0
7 1";
 
    using (TextReader stream = new StringReader(input1))
    {
        var res = Solve(stream);
        Console.WriteLine($"It is city {res.Item1}");
        Console.WriteLine($"Max value is {res.Item2}");
    }
}

@TopLayer · 31.03.2017, 15:59

Сообщение от Shamil1

Тогда решение

А такой инпут некорректный?

C#
1
2
3
4
    string input1 = 
@"2
20 10
10 20";

Добавлено через 6 минут
Полагаю крайний случай не учтен, но идея понятна

Добавлено через 8 минут
Надо слово else убрать из 16-й строки

@Shamil1 · 31.03.2017, 16:21

Решение:

У нас есть пары чисел (заправка, расход). Один шаг состотит в том, чтобы заправиться и доехать до следующего города. Изменение количества топлива за один шаг = заправка - расход.
Таким образом, у нас есть n чисел a_i. Нужно найти такое число, начиная с которого все промежуточные суммы неотрицательные. Для быстрого нахождения суммы любого отрезка, посчитаем все частичные суммы s_i.
Тогда для некого k промежуточные суммы будут равны [a_k..a_i] = s_i - s_k-1 (i > k) и [a_k..a_i] = (s_n-1 - s_k-1) + s_i = s_i - s_k-1 (i < k) (так как s_n-1 == 0). Причём, первое слагаемое одинаковое для всех a_k.
Минимум промежуточных сумм min(s_i - s_k-1) = min_si - min(s_k-1) = min_si - min_si = 0 будет при минимальном s_k-1.
Максимум промежуточных сумм для этого k max(s_i - s_k-1) = max_si - s_k-1 = max_si - min_si.

Добавлено через 2 минуты

Сообщение от TopLayer

Надо слово else убрать из 16-й строки

Да. Либо отдельно обрабатывать первый элемент (инициализировать mins и maxs значением первого элемента).

Новые блоги и статьи Все статьи Все блоги /
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .	Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	31.03.2017, 14:54
	Shamil1, видимо так, судя по посту 33. 0