c# - 我合并金矿的算法的缺陷在哪里？

Question

设置是，给定一个 N 对象的列表，例如

class Mine
{
    public int Distance { get; set; } // from river
    public int Gold { get; set; } // in tons
}

将黄金从一个矿山转移到另一个矿山的成本是

    // helper function for cost of a move
    Func<Tuple<Mine,Mine>, int> MoveCost = (tuple) => 
        Math.Abs(tuple.Item1.Distance - tuple.Item2.Distance) * tuple.Item1.Gold;

我想将黄金合并到 K 个矿山中。

我写了一个算法，想了很多遍，但不明白为什么它不起作用。希望我的意见有所帮助。知道我哪里出错了吗？

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Mine
{
    public int Distance { get; set; } // from river
    public int Gold { get; set; } // in tons
}

class Solution 
{
    static void Main(String[] args) 
    {
        // helper function for reading lines
        Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse);

        int[] line1 = LineToIntArray(Console.ReadLine());
        int N = line1[0], // # of mines
            K = line1[1]; // # of pickup locations

        // Populate mine info
        List<Mine> mines = new List<Mine>();
        for(int i = 0; i < N; ++i)
        {
            int[] line = LineToIntArray(Console.ReadLine());
            mines.Add(new Mine() { Distance = line[0], Gold = line[1] });
        }

        // helper function for cost of a move
        Func<Tuple<Mine,Mine>, int> MoveCost = (tuple) => 
            Math.Abs(tuple.Item1.Distance - tuple.Item2.Distance) * tuple.Item1.Gold;

        // all move combinations
        var moves = from m1 in mines
                    from m2 in mines
                    where !m1.Equals(m2)
                    select Tuple.Create(m1,m2);

        // moves in ascending order of cost
        var ordered = from m in moves
                      orderby MoveCost(m)
                      select m;

        int sum = 0; // running total of move costs
        var spots = Enumerable.Repeat(1, N).ToArray(); // spots[i] = 1 if hasn't been consildated into other mine, 0 otherwise
        var iter = ordered.GetEnumerator();
        while(iter.MoveNext() && spots.Sum() != K)
        {
            var move = iter.Current; // move with next smallest cost
            int i = mines.IndexOf(move.Item1), // index of source mine in move
                j = mines.IndexOf(move.Item2); // index of destination mine in move
            if((spots[i] & spots[j]) == 1) // if the source and destination mines are both unconsolidated
            {
                sum += MoveCost(move); // add this consolidation to the total cost
                spots[i] = 0; // "remove" mine i from the list of unconsolidated mines 
            }
        }

        Console.WriteLine(sum);
    }
}

我失败的测试用例的一个例子是

3 1
11 3
12 2
13 1

我的输出是

3

正确的输出是

4

Answer 1

另一个答案确实指出了实现中的一个缺陷，但它没有提到在您的代码中，您实际上并没有更改 Gold剩余值 Mine对象。因此，即使您确实对数据进行了重新排序，也无济于事。

此外，在每次迭代中，您真正关心的是最小 值。对整个数据列表进行排序是多余的。您只需扫描一次即可找到值(value)最低的商品。

您实际上也不需要单独的标志数组。只需在列表中维护您的移动对象，并在选择移动后，删除包含 Mine 的移动对象。否则你会被标记为不再有效。

这是您的算法的一个版本，其中包含上述反馈:

    static void Main(String[] args)
    {
        string input =
@"3 1
11 3
12 2
13 1";
        StringReader reader = new StringReader(input);

        // helper function for reading lines
        Func<string, int[]> LineToIntArray = (line) => Array.ConvertAll(line.Split(' '), Int32.Parse);

        int[] line1 = LineToIntArray(reader.ReadLine());
        int N = line1[0], // # of mines
            K = line1[1]; // # of pickup locations

        // Populate mine info
        List<Mine> mines = new List<Mine>();
        for (int i = 0; i < N; ++i)
        {
            int[] line = LineToIntArray(reader.ReadLine());
            mines.Add(new Mine() { Distance = line[0], Gold = line[1] });
        }

        // helper function for cost of a move
        Func<Tuple<Mine, Mine>, int> MoveCost = (tuple) =>
            Math.Abs(tuple.Item1.Distance - tuple.Item2.Distance) * tuple.Item1.Gold;

        // all move combinations
        var moves = (from m1 in mines
                    from m2 in mines
                    where !m1.Equals(m2)
                    select Tuple.Create(m1, m2)).ToList();

        int sum = 0, // running total of move costs
            unconsolidatedCount = N;
        while (moves.Count > 0 && unconsolidatedCount != K)
        {
            var move = moves.Aggregate((a, m) => MoveCost(a) < MoveCost(m) ? a : m);

            sum += MoveCost(move); // add this consolidation to the total cost
            move.Item2.Gold += move.Item1.Gold;
            moves.RemoveAll(m => m.Item1 == move.Item1 || m.Item2 == move.Item1);
            unconsolidatedCount--;    
        }

        Console.WriteLine("Moves: " + sum);
    }

如果您的问题没有提供更多详细信息，我无法保证这确实符合规范。但它确实产生了值 4对于 sum . :)