Как удалить два элемента коллекции одновременно? Задача про циклопы-линзы
Я не могу решить эту задачу.
- Есть N циклопов и массив из N элементов.
- Каждый элемент является ценностью зрения одиночного циклопа.
- Каждому циклопу нужна линза со значением К, но он сойдет и с объектив значения К+1 или К-1.
- Циклопы всегда покупают линзы парами.
Например, 5 циклопам со значениями зрения [1,-1,2,3,-3] нужно будет купить 3 пары линз.
Мне нужно написать программу, которая будет считать минимальное количество необходимых пар линз.
я пробовал вот так
int cyclops = 4;
int[] cyclopsSightValues = { 1, 7, 4, 1 };
if (cyclops < 2) { return 1;}
List<int> list = cyclopsSightValues .ToList();
int matchCount = 0;
for (int i = 0; i < list.Count; i++)
{
for (int j = 0; j < list.Count; j++)
{
if (list[i] == list[j] ||
list[i] + 1 == list[j] ||
list[i] + 2 == list[j] ||
list[i] - 1 == list[j] ||
list[i] - 2 == list[j])
{
int valueToRemove1 = list[i];
int valueToRemove2 = list[j];
list.Remove(valueToRemove1);
list.Remove(valueToRemove2);
matchCount++;
continue;
}
}
}
return matchCount + (cyclops-matchCount*2);
Я думаю, мне нужно найти совпадающие прицелы и удалить их из списка, но результат всегда получается меньше правильного на 1. Может моя логика вообще неверна? Любая помощь приветствуется.
Также представим, что 0-й циклопический прицел совпадает с 1-м и 3-м, 1-й соответствует 0-му, а 2-й и 3-й соответствует только 0-му. Если вы удалите 0-1 как пару, то 3-й не будет иметь пары (2-й тоже), но если вы соедините 0-3, то 1-2 также могут быть соединены.
Вы можете проявить уважение к тем, кто может попытаться помочь вам, приложив основные усилия, чтобы убедиться, что отступы в ваших примерах кода правильные, а не слишком правильные.
Ответы 2
Посмотрите, если у двух циклопов разница в зрении 2 или меньше по абсолютной величине, они могут купить линзы, которые подходят им обоим, например.
3 и 1 могут купить пару линз 2. А теперь попробуем применить жадный подход: упорядочить циклопов по их прицелу и попробовать
использовать линзы spare как можно чаще:
1, -1, 2, 3, -3 -> -3, -1, 1, 2, 3
-3 v -1, 1 v 2, 3
can use
-2 1
Пока все хорошо, все, что нам нужно сделать, это отсортировать и отсканировать:
private static int Solve(int[] cyclopsSightValues) {
Array.Sort(cyclopsSightValues);
int result = 0;
bool hasSpare = false;
for (int i = 0; i < cyclopsSightValues.Length; ++i)
if (hasSpare && cyclopsSightValues[i - 1] + 2 >= cyclopsSightValues[i])
hasSpare = false; // We use spare lense from the previous cyclope
else {
// we have to buy a pair, and now we have a spare lense
hasSpare = true;
result += 1;
}
return result;
}
Демо:
int[][] tests = {
new[] { 1, -1, 2, 3, -3 },
new int[] { },
new[] { 1, 1, 1, 1 },
};
string report = string.Join(Environment.NewLine, tests
.Select(item => $"[{string.Join(", ", item)}] => {Solve(item)}"));
Console.Write(report);
Выход:
[1, -1, 2, 3, -3] => 3
[] => 0
[1, 1, 1, 1] => 2
Пожалуйста, поиграйте сами
Не проверено, но должно более или менее работать:
public static IEnumerable<int> LensesToBuy(IEnumerable<int> cyclopsVisions)
{
int? buf = null;
var e = cyclopsVisions.OrderBy(v => v).GetEnumerator();
while(e.MoveNext())
{
if (!buf.HasValue)
{
buf = e.Current;
}
else if (Math.Abs(buf.Value - e.Current) > 2)
{ // cached value not compatible
yield return buf.Value;
buf = e.Current;
}
else
{ // cached value is compatible
if (buf.Value == e.Current) yield return buf.Value;
if (buf.Value > e.Current) yield return buf.Value - 1;
if (buf.Value < e.Current) yield return buf.Value + 1;
buf = null;
}
}
if (buf.HasValue) yield return buf.Value;
}
Назовите это так:
int[] cyclopsSightValues = { 1, 7, 4, 1 };
var result = LensesToBuy(cyclopsSightValues); //okay to pass array
Console.WriteLine(result.Count());
«Я пробовал так» - и что пошло не так (подсказка, 1) когда вы удаляете элемент из списка, остальная его часть сдвигается, что приводит к уменьшению индексов всех оставшихся значений 2)
Removeудалит все совпадающие значения, поэтому.Remove(1)будет удалить все1sв списке)