ACM/ICPC 2009 武汉现场赛 Download Manager 题解
这是一道模拟的题目。
我的思路是，用两个优先队列，一个是正在下载的文件的队列，另一个是等待下载的文件的队列。对于正在下载的文件队列，维护“所剩字节数最少的那个文件”在堆顶；对于等待下载的文件的队列，维护题目中所描述的那种最优先被下载的文件在堆顶。
然后循环，看正在下载的文件队列是否满，未满则将等待被下载的文件队列中的文件一个个弹出又插入到正在下载的队列。再看那个所剩字节最少的文件，让每个文件都减掉那么多字节，然后把那些字节为 0（即下载完了的）文件删掉，再把所需时间加到计数器。最后循环啊循环就好了。
这道题有一个阴险的地方是：
Print a blank line after the output of each test case.
害我 WA 了两次……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include <queue> #include <cstdio> #include <vector> #include <algorithm> using namespace std; struct file { double size, progress, remain; inline file(double sz, double pg) : size(sz), progress(pg) { remain = size - size * progress / 100.0; } inline bool operator<=(const file &b) const { if (size == b.size) return progress >= b.progress; return size <= b.size; } }; class download_priority { public: inline bool operator()(const file &a, const file &b) { return b <= a; } }; class remaining_size { public: inline bool operator()(const file &a, const file &b) { return a.remain >= b.remain; } }; int file_count, max_download; double bandwidth; vector<file> download_slot; priority_queue<file, vector<file>, download_priority> download_queue; inline void fill_download_slot() { while (download_slot.size() < max_download && !download_queue.empty()) { download_slot.push_back(download_queue.top()); download_queue.pop(); push_heap(download_slot.begin(), download_slot.end(), remaining_size()); } } inline void decrease_remain_by(double size) { for (int i = 0; i < download_slot.size(); ++i) download_slot[i].remain -= size; } inline void remove_downloaded_files() { while (!download_slot.empty() && download_slot[0].remain <= 0.0) { pop_heap(download_slot.begin(), download_slot.end(), remaining_size()); download_slot.pop_back(); } } inline double download_time() { double second = 0.0; while (!download_slot.empty() || !download_queue.empty()) { fill_download_slot(); double bandwidth_each = bandwidth / (double)download_slot.size(); // File with least download-time will be download_slot[0]. double remain_size = download_slot[0].remain; double remain_time = remain_size / bandwidth_each; decrease_remain_by(remain_size); remove_downloaded_files(); second += remain_time; } return second; } inline bool init_and_input() { scanf("%d %d %lf", &file_count, &max_download, &bandwidth); if (file_count == 0.0 && max_download == 0.0 && bandwidth == 0.0) return false; for (int i = 0; i < file_count; ++i) { double size, progress; scanf("%lf %lf", &size, &progress); download_queue.push(file(size, progress)); } return true; } int main() { // freopen("input.txt", "r", stdin); int i = 0; while (init_and_input()) printf("Case %d: %0.2lf\n\n", ++i, download_time()); return 0; } |
