2.5.13

2.5.13 #

解答 #

官方解答见：https://algs4.cs.princeton.edu/25applications/LPT.java.html

使用上题的 Job 类，在本题建立 Processor 类来代表处理器，定义如下：

internal class Processor : IComparable<Processor>
{
    private readonly List<Job> _jobs = new();
    private double _busyTime;

    public void Add(Job job)
    {
        _jobs.Add(job);
        _busyTime += job.Time;
    }

    public int CompareTo(Processor other)
    {
        return _busyTime.CompareTo(other._busyTime);
    }

    public override string ToString()
    {
        var sb = new StringBuilder();
        var nowList = _jobs.ToArray();
        for (var i = 0; i < nowList.Length; i++)
        {
            sb.AppendLine(nowList[i].Name + " " + nowList[i].Time);
        }

        return sb.ToString();
    }
}

按照读入所有的任务并排序，再将所有的处理器放进一个最小堆里。

从最小堆取出任务最轻的处理器，按取耗时最长的任务分配给它，再将它放回最小堆中。

最后依次打印处理器的任务分配即可。

代码 #

using System;
using System.Collections.Generic;
using System.Text;
using SortApplication;
// ReSharper disable AssignNullToNotNullAttribute
// ReSharper disable PossibleNullReferenceException

var processorNum = int.Parse(Console.ReadLine());
var jobNum = int.Parse(Console.ReadLine());

var jobs = new Job[jobNum];
for (var i = 0; i < jobNum; i++)
{
    var jobDesc = Console.ReadLine().Split(' ');
    jobs[i] = new Job(jobDesc[0], double.Parse(jobDesc[1]));
}

Array.Sort(jobs);

var processors = new MinPq<Processor>(processorNum);
for (var i = 0; i < processorNum; i++)
{
    processors.Insert(new Processor());
}

for (var i = jobs.Length - 1; i >= 0; i--)
{
    var min = processors.DelMin();
    min.Add(jobs[i]);
    processors.Insert(min);
}

while (!processors.IsEmpty())
{
    Console.WriteLine(processors.DelMin());
}

internal class Job : IComparable<Job>
{
    public readonly string Name;
    public readonly double Time;

    public Job(string name, double time)
    {
        Name = name;
        Time = time;
    }

    public int CompareTo(Job other)
    {
        return Time.CompareTo(other.Time);
    }
}

internal class Processor : IComparable<Processor>
{
    private readonly List<Job> _jobs = new();
    private double _busyTime;

    public void Add(Job job)
    {
        _jobs.Add(job);
        _busyTime += job.Time;
    }

    public int CompareTo(Processor other)
    {
        return _busyTime.CompareTo(other._busyTime);
    }

    public override string ToString()
    {
        var sb = new StringBuilder();
        var nowList = _jobs.ToArray();
        for (var i = 0; i < nowList.Length; i++)
        {
            sb.AppendLine(nowList[i].Name + " " + nowList[i].Time);
        }

        return sb.ToString();
    }
}

另请参阅 #

SortApplication 库