Дана задача:
Толик придумал новую технологию программирования. Он хочет уговорить друзей использовать ее. Однако все не так просто. 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. И при этом мне недоступна вообще никакая информация даже о том, при каких входных данных допущена ошибка. Дан только один пример входных / выходных данных, который программа успешно проходит.
Как мне или не совершать ошибок, или понимать, что я сделал не так? Сейчас я вижу только возможность того, что порядок привлечения "плохих культистов" может быть не всегда оптимальным, но он вроде и так сложный, как-то слабо верится, что там действительно может быть необходим ещё более сложный алгоритм выбора.
Если дадите мне рабочее решение, тоже буду благодарен, но мне бы самому научиться...
