设置是,给定一个类似的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
另一个答案确实指出了实现中的一个缺陷,但它没有提到在您的代码中,您实际上并没有更改其余Mine
对象中的Gold
值。因此,即使您确实对数据进行了重新排序,也无济于事。
此外,在每次迭代中,您真正关心的只是最小值。对整个数据列表进行排序是过分的。您只需扫描一次即可找到价值最低的项目。
您也不需要单独的标志数组。只需将移动对象保留在列表中,选择移动后,删除包含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);
}
如果你的问题没有更多细节,我不能保证这真的符合规范。但它确实为sum
生成值4
。:)
当您将矿山i合并为矿山j时,矿山1中的黄金量会增加。这使得从矿山j到其他矿山的整合成本更高,可能会使移动成本对矿山的排序无效。为了解决这个问题,您可以在while循环的每次迭代开始时对地雷列表进行重新排序。