Задать вопрос
@OrdUs

При каких входных данных моя программа работает неверно и как мне научиться самому это понимать? Как научиться искать ошибки?

Дана задача:

Толик придумал новую технологию программирования. Он хочет уговорить друзей использовать ее. Однако все не так просто. i-й друг согласится использовать технологию Толика, если авторитет Толика будет не меньше a_i
(авторитет выражается целым числом). Как только i-й друг начнет ее использовать, к авторитету Толика прибавится число b_i (попадаются люди, у которых b_i < 0). Помогите Толику наставить на путь истинный как можно больше своих друзей.

Входные данные: В первой строке содержатся два целых числа: Количество друзей у Толика n (1 <= n <= 10^5) и первоначальный авторитет Толика a_0 (−109≤a0≤109). Следующие n строк содержат пары целых чисел a_i и b_i (−109≤ai, bi≤109).

Выходные данные
В первой строке выведите число m − максимальное число друзей, которых может увлечь Толик. Во второй строке выведите m чисел − номера друзей в том порядке, в котором их нужно агитировать.

Моё решение:
public static class Authority
{
    public static string GetMaxCultists(long authority, long[][] potential_cultists)
    {
        // Первый элемент подмассива массива (отдельного потенциального культиста) — a_i, второй — b_i, третий — его номер
        potential_cultists = potential_cultists.OrderBy(x => x[0]).ToArray(); // Сортировка культистов по требуемому авторитету

        long max_cultist_count = 0; // output
        string steps = ""; // Шаги

        List<long[]> bad_cultists = new List<long[]>(); // Культисты, авторитет уменьшающие

        for (int i = 0, end = potential_cultists.Length; i < end; i++)
        {
            if (potential_cultists[i][1] < 0) // Если потенциальный культист авторитет уменьшает, оставляем его на потом
            {
                bad_cultists.Add(potential_cultists[i]);
                continue;
            }

            if (authority >= potential_cultists[i][0]) // Если авторитета хватает для вступления друга в ряды культистов, принимаем его
            {
                max_cultist_count++;
                authority += potential_cultists[i][1];
                steps = $"{steps} {potential_cultists[i][2]}";
            }

            else break; // Если авторитета не хватает, то и на следующих не хватит, так что выходим из цикла
        }



        bad_cultists = bad_cultists.OrderBy(x => x[1]).ToList(); // Отсортирован по возрастанию уменьшения авторитета
        List<long[]> bad_cultists_sorted_by_required_authority = bad_cultists.OrderByDescending(x => x[0]).ThenByDescending(x => x[1]).ToList(); // Отсортирован по убыванию необходимого авторитета

        while (bad_cultists.Count > 0)
        {
            if (authority >= bad_cultists[0][0])
            {
                if (bad_cultists_sorted_by_required_authority[0][0] > authority + bad_cultists[0][1]) // Если наименьшего уменьшения авторитета достаточно, чтобы требующий наибольшего авторитета друг не стал культистом
                {
                    if (bad_cultists_sorted_by_required_authority[0][0] > authority) // Если авторитета так и так не хватит, просто удалить и забить
                    {
                        bad_cultists.Remove(bad_cultists_sorted_by_required_authority[0]);
                        bad_cultists.RemoveAt(0);
                    }

                    else // А если авторитета хватит на вступление в ряды культистов требующего наибольшего авторитета друга, присоединить
                    {
                        authority += bad_cultists_sorted_by_required_authority[0][1];

                        steps = $"{steps} {bad_cultists_sorted_by_required_authority[0][2]}";
                        max_cultist_count++;

                        bad_cultists.Remove(bad_cultists_sorted_by_required_authority[0]);
                        bad_cultists_sorted_by_required_authority.RemoveAt(0);
                    }
                }

                else // Если всё норм, то всё норм
                {
                    authority += bad_cultists[0][1];

                    steps = $"{steps} {bad_cultists[0][2]}";
                    max_cultist_count++;

                    bad_cultists_sorted_by_required_authority.Remove(bad_cultists[0]);
                    bad_cultists.RemoveAt(0);
                }
            }

            else // Если друг с наименьшим уменьшением авторитета не может стать культистом, удаляем его
            {
                bad_cultists_sorted_by_required_authority.Remove(bad_cultists[0]);
                bad_cultists.RemoveAt(0);
            }
        }

        return $"{max_cultist_count}\n{steps.Trim()}";
    }




    static void Main() // Тестирование метода
    {
        string input = Console.ReadLine();
        long[] inp_array = input.Split().Select(x => long.Parse(x)).ToArray();


        long start_authority = inp_array[1];
        long[][] potential_cultists = new long[inp_array[0]][];

        for (long i = 0, end = inp_array[0]; i < end; i++)
        {
            inp_array = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();
            potential_cultists[i] = new long[] { inp_array[0], inp_array[1], i + 1 };
        }

       Console.WriteLine(Authority.GetMaxCultists(start_authority, potential_cultists));
    }
}

Это решение прошло только 4 теста из 25. И при этом мне недоступна вообще никакая информация даже о том, при каких входных данных допущена ошибка. Дан только один пример входных / выходных данных, который программа успешно проходит.
Как мне или не совершать ошибок, или понимать, что я сделал не так? Сейчас я вижу только возможность того, что порядок привлечения "плохих культистов" может быть не всегда оптимальным, но он вроде и так сложный, как-то слабо верится, что там действительно может быть необходим ещё более сложный алгоритм выбора.
Если дадите мне рабочее решение, тоже буду благодарен, но мне бы самому научиться...
  • Вопрос задан
  • 5 просмотров
Подписаться 1 Средний Комментировать
Помогут разобраться в теме Все курсы
  • OTUS
    C# Developer. Professional
    6 месяцев
    Далее
  • Ulearn.me
    Основы программирования на примере C#. Часть 1
    1 неделя
    Далее
  • Ulearn.me
    Основы программирования на примере C#. Часть 2
    1 неделя
    Далее
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы