前言
前两节已经分析过题解，也梳理了二叉堆与优先队列的实现方式，今天完成洗衣机烘干机的问题。
题目
后来我查，这是一道ACM的题，原题链接
- 1、有m个洗衣机，每台洗衣机只能一件一件洗，没台洗衣机的时间不同。
- 2、有n个烘干机，每台烘干机只能一件一件烘干，没台烘干机的时间不同。
- 3、一共有x件衣服，每件衣服要先洗干净，然后再烘干。
- 求：处理完所有衣服最少的时间是多少？
实现
public class WashTest {
// m个洗衣机
private static final int COUNT_M = 0;
// n个烘干机
private static final int COUNT_N = 0;
// x件衣服
private static final int COUNT_L = 0;
// m个洗衣机,数组记录每个洗衣机耗时时间
int[] m = new int[COUNT_M];
// m个洗衣机,数组记录每个洗衣机耗时时间
int[] n = new int[COUNT_N];
int getTotalCostTime(int[] m, int[] n, int l) {
// 构建洗衣机最小堆
PriorityQueue washPQ = new PriorityQueue<WashModel>(m.length);
for (int i = 0; i < m.length; i++) {
WashModel washModel = new WashModel(i, m[i]);
washPQ.push(washModel);
}
// 构建烘干机最小堆
PriorityQueue hongPQ = new PriorityQueue<WashModel>(n.length);
for (int i = 0; i < n.length; i++) {
WashModel washModel = new WashModel(i, n[i]);
hongPQ.push(washModel);
}
// 存储每件衣服洗涤的时间
int[] costL = new int[l];
for (int i = 0; i < l; i++) {
// 取出当前洗完最快就绪的洗衣机
WashModel washModel = (WashModel) washPQ.pop();
// 记录
costL[i] = washModel.getTime();
// 将当前衣服重新加入最小堆
washModel.setTime(washModel.getTime() + m[washModel.getIndex()]);
washPQ.push(washModel);
}
// 记录耗时最长的一件衣服
int res = 0;
// 倒着从洗衣机完成的衣服中取出,让最后意见洗完的衣服找到最快的烘干机
for (int i = l - 1; i >= 0; i--) {
// 取出当前洗完最快就绪的洗衣机
WashModel washModel = (WashModel) hongPQ.pop();
// 比较每一件衣服烘干完的时间
res = Math.max(res,washModel.getTime()+costL[i]);
// 加上烘干时间
washModel.setTime(washModel.getTime()+n[washModel.getIndex()]);
// 重新插入优先队列
hongPQ.push(washModel);
}
return res;
}
class WashModel implements Comparable<WashModel> {
private int index;
private int time;
public WashModel(int index, int time) {
this.index = index;
this.time = time;
}
@Override
public int compareTo(WashModel o) {
return this.time - o.time;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public int getTime() {
return time;
}
public void setTime(int time) {
this.time = time;
}
}
}
class BinaryHeap<T extends Comparable> {
// 用数组作为二叉堆的底层存储结构
private T[] values;
// 当前二叉堆实际存储的元素数量
private int count;
// 构造函数,初始化是决定堆大小
public BinaryHeap(int capacity) {
this.values = (T[]) new Comparable[capacity + 1];
}
/**
* 取出堆顶元素
*
* @return
*/
public T pop() {
// 先取出堆顶元素
T result = values[1];
// 和堆底元素进行交换
exchange(1, count);
// 清除堆顶元素(此时堆顶元素在堆底)
values[count--] = null;
// 将新插入的元素进行下沉
down(1);
return result;
}
/**
* 插入元素
*
* @param target
*/
public void insert(T target) {
// 将新元素添加在最后
values[++count] = target;
// 上浮新插入的元素
up(count);
}
/**
* 获取target的父节点下标
*
* @param target
* @return
*/
private int parent(int target) {
return target / 2;
}
/**
* 获取target的左节点下标
*
* @param target
* @return
*/
private int left(int target) {
return target * 2;
}
/**
* 获取target的右节点下标
*
* @param target
* @return
*/
private int right(int target) {
return target * 2 + 1;
}
/**
* 上浮
*
* @param target
*/
private void up(int target) {
// target = 1 时代表到了堆顶,不再交换
// 与父节点比较,直到一个比自己小的父节点
while (target > 1 && large(parent(target), target)) {
exchange(parent(target), target);
}
}
/**
* 下沉
*
* @param target
*/
private void down(int target) {
// 判断是否已经到了堆底
while (left(target) <= count) {
// 找到左右节点的较小节点
int smaller = left(target);
if (right(target) <= count && large(smaller, right(target))) {
smaller = right(target);
}
// 和左右子节点中较小的比较,如果比较小的小,就不需要下沉了
if (large(smaller, target)) {
return;
}
// 与较小的子节点交换位置
exchange(smaller, target);
// 更新要比较的目标节点坐标
target = smaller;
}
}
/**
* 交换两节点位置
*
* @param index1
* @param index2
*/
private void exchange(int index1, int index2) {
T tmp = values[index1];
values[index1] = values[index2];
values[index2] = values[1];
}
/**
* 比较两节点大小
*
* @param index1
* @param index2
* @return
*/
private boolean less(int index1, int index2) {
// 返回index1的值是否比index2的值小
return values[index1].compareTo(index2) < 0;
}
/**
* 比较两节点大小
*
* @param index1
* @param index2
* @return
*/
private boolean large(int index1, int index2) {
// 返回index1的值是否比index2的值小
return values[index1].compareTo(index2) > 0;
}
}
class PriorityQueue<T extends Comparable> {
private BinaryHeap<T> binaryHeap;
public PriorityQueue(int capacity) {
this.binaryHeap = new BinaryHeap(capacity);
}
public void push(T t) {
this.binaryHeap.insert(t);
}
public T pop() {
return this.binaryHeap.pop();
}
}
网友评论