Tôi đã cố gắng suy nghĩ từ HOURS về vấn đề TopCoder này và không thể đi kèm với một giải pháp hoàn hảo làm việc và tìm thấy một đưa ra dưới đây là điên rồ đẹp được sử dụng!Tại sao mã này hoạt động cho trình thăm dò TopCoder này?
Tôi đang cố gắng tìm ra cách giải pháp này hoạt động đối với probem đã cho? Và làm thế nào tôi có thể nghĩ ban đầu về nó? Sau khi đọc giải pháp tôi đã nhận ra đó là một biến thể của mã Huffman nhưng đó là điều tôi có thể nhận được. Tôi thực sự say mê và muốn biết những gì dòng suy nghĩ có thể dẫn đến giải pháp này ..
Dưới đây là các vấn đề: http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091
Fox Ciel có rất nhiều bài tập về nhà để làm. Bài tập về nhà bao gồm một số nhiệm vụ cùng nhau độc lập. Các nhiệm vụ khác nhau có thể lấy các số tiền khác nhau thời gian để hoàn thành. Bạn được cung cấp một int [] workCost. Đối với mỗi i, nhiệm vụ thứ i là sẽ mất tối đa [i] giây để hoàn thành. Cô ấy muốn tham dự một bữa tiệc và gặp gỡ bạn bè của cô ấy, do đó cô ấy muốn hoàn thành tất cả các nhiệm vụ nhanh nhất có thể.
Vấn đề chính là tất cả các con cáo, kể cả Ciel, thực sự ghét làm bài tập về nhà . Mỗi con cáo chỉ sẵn sàng làm một trong các nhiệm vụ. May mắn thay, Đôrêmon, một con mèo robot từ thế kỷ 22, đã cho Fox Ciel một cái búa chia tách : một tiện ích ma thuật có thể tách bất kỳ con cáo nào thành hai con cáo.
Bạn được cung cấp một phân tách int. Sử dụng búa tách trên con cáo là tức thời. Khi một cái búa được sử dụng trên một con cáo, con cáo sẽ bắt đầu tách ra là . Sau khi splitCost giây cô sẽ biến thành hai con cáo - con cáo ban đầu và một con cáo hoàn toàn mới. Trong khi một con cáo đang tách ra, nó không được phép sử dụng cây búa trên cô ấy một lần nữa.
Công việc trên một tác vụ không thể bị gián đoạn: một khi con cáo bắt đầu làm việc trên một nhiệm vụ, cô ấy phải hoàn thành nó. Nó không được phép cho nhiều con cáo để hợp tác trên cùng một nhiệm vụ. Con cáo không thể thực hiện nhiệm vụ khi cô ấy đang bị chia nhỏ bằng búa. Có thể chia cùng một con cáo nhiều lần. Có thể chia một con cáo cả trước và sau cô ấy giải quyết một trong các nhiệm vụ.
Tính toán và trả lại khoảng thời gian nhỏ nhất mà các cáo có thể giải quyết tất cả các tác vụ.
Và đây là giải pháp tôi tìm thấy tại đây link
import java.util.*;
public class FoxAndDoraemon {
public int minTime(int[] workCost, int splitCost) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for(int i : workCost) pq.offer(i);
while(pq.size()>=2) {
int i = pq.poll();
int j = pq.poll();
pq.offer(Math.max(i, j) + splitCost);
}
return pq.poll();
}
}
Hàng đợi ưu tiên có trả về phần tử tối đa hoặc phần tử min khi bạn thăm dò ý kiến không? – ElKamina
Ít nhất. Hàng đợi ưu tiên được sắp xếp từ ít nhất đến phần tử lớn nhất và giữ lại phân loại của chúng trên chèn. – Charles
Câu trả lời này có vẻ không chính xác. Hãy xem xét 'minTime (new int [] {1, 1, 1}, 5)'. Rõ ràng điều đúng đắn cần làm là không song song với bất kỳ nhiệm vụ nào, do đó phải mất 3 giây. Giải pháp này sẽ cung cấp cho 11s! –