Лучший результат из нескольких списков

Question

У меня есть список списков, содержащий KeyValuePair<int, double>, отсортированный по двойному, где int означает ID и double означает Оценка для этогоЯ БЫ.Я хотел бы создать алгоритм, который дает мне top-k идентификаторов, где сумма идентификаторов максимизируется.Теперь я знаю, как это сделать, но я не знаю, как реализовать это в c #.

Так что идея состоит в том, чтобы взять первый элемент каждого списка и вычислить «порог», суммуоценки этой строки, которые являются максимальным значением, которое может быть суммой.Затем мы просматриваем всю сумму баллов идентификаторов в этой строке и помещаем ее в буфер.Затем мы переходим к следующему ряду и вычисляем порог и оценки, и если одна из оценок в буфере превышает текущее пороговое значение, мы знаем, что он должен быть в топ-ке, помещаем его туда и продолжаем, пока у нас не будетзначения к.Я надеюсь, что есть кто-нибудь, кто может указать мне правильное направление.

Некоторые примеры данных: в списке есть списки буксиров:

{(1, 25), (2, 23), (3, 19), (4, 10), (5, 3)}, 
{(2, 24), (3, 20), (1, 15), (5, 10), (4, 3)}

После первого раунда мыимеют порог 25+24 = 49, а буфер состоит из (1, 40) и (2, 47).Мы переходим к следующей строке и находим значения (2, 23) и (3, 20), поэтому порог равен 43, и мы добавляем (3, 39) в буфер.Мы видим в буфере, что кортеж с идентификатором 2 имеет оценку выше порогового значения, поэтому мы добавляем его в Top-k.

Списки содержат до 100000 KeyValuePairs, и смысл состоит в том, чтобы обрабатывать тольконесколько KeyValuePairs, чтобы найти top-k, вместо того, чтобы просто подсчитать счет для каждого кортежа и взять top-k.

Answer 1

Если вы хотите суммировать список пар «ключ-значение» на Key, где счет равен Value, вы можете сделать это довольно просто, используя Linq, например, чтобы получить 2 лучших игрока:

var playerScores = new List<KeyValuePair<int, double>>() {
    new KeyValuePair<int, double>(1, 1.0),
    new KeyValuePair<int, double>(2, 20.0),
    new KeyValuePair<int, double>(3, 10.8),
    new KeyValuePair<int, double>(1, 15.2),
    new KeyValuePair<int, double>(2, 10.2),
    new KeyValuePair<int, double>(3, 8.4),
    new KeyValuePair<int, double>(1, 3),
    new KeyValuePair<int, double>(2, 6.6),
    new KeyValuePair<int, double>(3, 9.2),
};

var totalScores = playerScores
    .GroupBy(a => a.Key)
    .Select(g => new { id = g.Key, total = g.Sum(gk => gk.Value) })
    .OrderByDescending(x => x.total);

foreach (var player in totalScores.Take(2)) // find the top 2 scores
{
    Console.WriteLine($"player {player.id} scores {player.total}");
}

выход:

player 2 scores 36.8
player 3 scores 28.4