Обновление : Гах, я не заметил, что у вас, кажется, есть только 4 элемента в списке.Ответ здесь для общего случая, и будет излишним для 4-элементной задачи.Продолжайте цикл.
Ну, лично я бы использовал структуру данных Heap, где каждый элемент - это значение каждого элемента + его позиция в исходном списке.
Вам нужновыследить хорошую реализацию кучи для C #, хотя.Вы можете использовать мой, но он является частью большой библиотеки классов, так что это может быть немного резиновый шарик, чтобы втянуть в ваш проект.Код здесь: Мой Mercurial Repository .
Ниже я приведу примеры того, как будет работать моя реализация.
Если вы не знаете, как работает кучаработает, это в основном структура данных, которая выглядит как массив, но также как дерево, где узлы дерева хранятся в массиве.Здесь задействовано немного кода, который «разумно» перемещает элементы.Прелесть этого в том, что очень просто получить самый высокий или самый низкий элемент (то есть один из них, а не оба из одной кучи), поскольку он всегда будет первым элементом в массиве.
Итак, я бы сделал следующее:
- Создание кучи, содержащей значение + позиция для всех элементов, отсортированных так, чтобы наибольшее значение было первым
- Создание кучи, содержащей значение+ позиция для всех элементов, отсортированная так, чтобы наименьшее значение было первым
Затем, если сумма <0, возьмите первый элемент кучи (значение + позиция), увеличьте значение висходный список на 1, затем <em>заменить первый элемент кучи на (значение + 1), положение.Замена первого элемента кучи приводит к его удалению, а затем к чтению, что может переместить его в другое положение, чем первое, если оно больше не является самым высоким / самым низким значением.Например, предположим, у вас есть следующий список:
list: 1, 2, 3
Куча теперь выглядит так:
heap: (1, 0), (2, 1), (3, 2) <-- second value is position, 0-based
т.е.Вы строите это так:
position: 0, 1, 2
list: 1, 2, 3
| | +-------+
| | |
+-+ +--+ |
| | |
<-+> <-+> <-+>
heap: (1, 0), (2, 1), (3, 2)
Теперь, если сумма слишком мала, вы берете первый элемент lo-heap, который равен (1, 0), увеличиваете значение в позиции 0 вИсходный список на 1, затем замените первый элемент кучи (который по-прежнему (1, 0)) новым элементом, содержащим новое значение, в той же позиции.
После замены список и куча теперьвыглядит так:
list: 2, 2, 3
heap: (2, 0), (2, 1), (3, 1)
Допустим, сумма все еще мала, поэтому повторите.Теперь, при повторном добавлении (3, 0) вместо (2, 0), оно будет немного сдвинуто обратно в кучу, поэтому оно выглядит следующим образом:
list: 3, 2, 3
heap: (2, 1), (3, 0), (3, 1)
Теперь значение 2 теперьсамый низкий, и, следовательно, первый элемент кучи.Обратите внимание, что эти операции не переупорядочивают всю кучу, а только необходимые части.Таким образом, куча идеальна для таких алгоритмов, поскольку их дешево сортировать при внесении изменений.
Итак, давайте посмотрим некоторый код.Я предполагаю, что у вас есть массив значений, подобных этому:
int[] values = new int[] { ... };
Таким образом, с моей реализацией кучи, следующее будет делать то, что вы хотите:
using System;
using System.Collections.Generic;
using System.Linq;
using LVK.DataStructures.Collections;
namespace SO3045604
{
class LowestComparer : IComparer<Tuple<int, int>>
{
public int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
return x.Item1.CompareTo(y.Item1);
}
}
class HighestComparer : IComparer<Tuple<int, int>>
{
public int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
return -x.Item1.CompareTo(y.Item1);
}
}
class Program
{
static void Main(string[] args)
{
int[] values = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
var valuesWithPositions = values
.Select((value, index) => Tuple.Create(value, index));
var loHeap = new Heap<Tuple<int, int>>(
new LowestComparer(),
valuesWithPositions);
var hiHeap = new Heap<Tuple<int, int>>(
new HighestComparer(),
valuesWithPositions);
int sum = values.Aggregate((a, b) => a + b);
while (sum < 75)
{
var lowest = loHeap[0];
values[lowest.Item2]++;
loHeap.ReplaceAt(0,
Tuple.Create(lowest.Item1 + 1, lowest.Item2));
sum++;
}
while (sum > 55)
{
var highest = hiHeap[0];
values[highest.Item2]--;
hiHeap.ReplaceAt(0,
Tuple.Create(highest.Item1 - 1, highest.Item2));
sum--;
}
// at this point, the sum of the values in the array is now 55
// and the items have been modified as per your algorithm
}
}
}