Я пытаюсь решить 11321 - Сортировка! Сортировать!! и сортировка !!! с использованием C #, прямой перевод моих решений (а также других людей) из cpp и Java.
Моя проблема в том, что listName.Sort() или Array.Sort(listName, ...Comparer.Create()...) неправильно сортирует выходные данные во время первого прохода. Мне нужно дважды позвонить, чтобы правильно отсортировать.
В некоторых случаях я вручную устанавливаю контрольные точки внутри CompareTo () при вызове Array.Sort, специально добавляю ссылку в список внутри замыкания, чтобы я мог наблюдать значения по мере их сортировки и сортировки должным образом до окончания Возвращает метод Array.Sort (), в котором затем я вижу, что некоторые значения возвращаются в неправильный порядок.
Я использую контрольные примеры Морасса из uDebug для проверки, и один пример неверного результата сортировки, который я получаю, находится в строке 10919 вывода:
Accepted My Output
10919 457 10919 461
10920 461 10920 457
Как видите, числа 461 и 457 должны быть отсортированы в порядке возрастания их значения по модулю 500, которое составляет 461 и 457 соответственно. Если я снова вызову метод сортировки в моем коде ниже, то я наконец получу правильный вывод.
Полагаю, мой вопрос: почему это происходит? Что-то не так с моей реализацией? Мои реализации представляют собой почти однозначные переводы принятого кода Java или cpp. Обратите внимание, что я также пытался использовать OrderQy () LINQ, который дает разные результаты, но в конечном итоге правильный, когда вызывается достаточное количество раз.
У меня есть следующий класс Number с соответствующей реализацией IComparable:
class Number : IComparable<Number>
{
public int Value { get; }
public int Mod { get; }
public bool IsOdd { get; }
public Number(int val, int mod)
{
Value = val;
Mod = mod;
IsOdd = val % 2 != 0;
}
public int CompareTo(Number other)
{
var leftVal = Value;
var leftMod = Mod;
var rightVal = other.Value;
var rightMod = other.Mod;
var leftOdd = IsOdd;
var rightOdd = other.IsOdd;
if (leftMod < rightMod) return -1;
else if (leftMod > rightMod) return 1;
else
{
if (leftOdd && rightOdd)
{
return leftVal > rightVal ? -1 : 1;
}
else if (!leftOdd && !rightOdd)
{
return leftVal > rightVal ? 1 : -1;
}
else if (leftOdd)
{
return -1;
}
else// (rightOdd)
{
return 1;
}
}
}
}
И мой основной метод:
public static void Main(string[] args)
{
while (true)
{
var settings = Console.ReadLine().Split(' ');
var N = int.Parse(settings[0]);
var M = int.Parse(settings[1]);
if (N == 0 && M == 0) break;
Console.WriteLine($"{N} {M}");
var output = new List<Number>();
var i = 0;
while (i < N)
{
var line = Console.ReadLine();
var val = int.Parse(line);
var mod = val % M;
output.Add(new Number(val, mod));
i++;
}
output.Sort();
// uncomment to produce acceptable answer
// output.Sort();
foreach (var line in output)
{
Console.WriteLine(line.Value);
}
}
Console.WriteLine("0 0");
}
Редактировать 1:
Просто обратите внимание, что я перенаправляю stdin и stdout из файла / в StringBuilder, поэтому я могу автоматизировать тестирование.
static void Main(string[] args)
{
var builder = new StringBuilder();
var output = new StringWriter(builder);
Console.SetOut(output);
var solution = File.ReadAllText("P11321_Outputs");
var problem = new StreamReader("P11321_Inputs");
Console.SetIn(problem);
P11321_1.Main(args);
}
Редактировать 2:
Вот часть тестового примера, где происходит странное поведение. Конкретный шаг воспроизведения заключается в том, что если вы измените контрольный пример, чтобы в нем было только 38 элементов, и удалили 11 из входных данных, то сортировки 457 и 461 будут выполнены правильно.
Введите:
39 500
-121
582
163
457
-86
-296
740
220
-867
-333
-773
11
-446
-259
-238
782
461
756
-474
-21
-358
593
548
-962
-411
45
-604
-977
47
-561
-647
926
578
516
382
-508
-781
-322
712
0 0
Выход:
39 500
-977
-474
-962
-446
-411
-867
-358
-333
-322
-296
-781
-773
-259
-238
-647
-121
-604
-86
-561
-21
-508
11
516
45
47
548
578
582
593
163
712
220
740
756
782
382
926
457
461
0 0