2.5.13

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

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

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

class Processor : IComparable<Processor>
{
    private List<Job> jobs = new List<Job>();
    private double busyTime = 0;

    public Processor() { }

    public void Add(Job job)
    {
        this.jobs.Add(job);
        this.busyTime += job.Time;
    }

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

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        Job[] nowList = this.jobs.ToArray();
        for (int 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;

namespace _2._5._13
{
    class Program
    {
        class Job : IComparable<Job>
        {
            public string Name;
            public double Time;

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

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

        class Processor : IComparable<Processor>
        {
            private List<Job> jobs = new List<Job>();
            private double busyTime = 0;

            public Processor() { }

            public void Add(Job job)
            {
                this.jobs.Add(job);
                this.busyTime += job.Time;
            }

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

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

        static void Main(string[] args)
        {
            int processorNum = int.Parse(Console.ReadLine());
            int jobNum = int.Parse(Console.ReadLine());

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

            Array.Sort(jobs);

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

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

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

另请参阅

SortApplication 库

上一题 下一题