博文
Zju 1200 Mining(2006-12-23 15:54:00)
摘要：
2178592
2006-12-23 15:29:25
Accepted
1200
C++
00:00.00
428K
Crux.D
堆维护。这个模拟题根本没有思路，看了论坛上AndyZh的算法才明白的。
把每个机器人到达矿区的时间排序，从中选出最小时间，然后更新此时间，重排堆。
（最小）堆排的算法是：与下面子节点中较小的节点比较，大则交换，小则停止。
#include <cstdio>
int s, w, c, l, m, h[10000], t, ans;
bool init()
{
if (scanf("%d", &s) == EOF) return false;
scanf("%d %d %d %d", &w, &c, &l, &m);
int i;
ans = 0, t = 9999 / c + 1;
if(l > t) l = t;
for(i = 0; i < t; i ++)
h[i] = m * i + m + s;
return true;
}
void push()
{
int cur = 0, j = h[0], next = cur * 2 + 1;; // h[0] min
if(ans < h[0]) ans = h[0];
h[cur] += s + s + w; ans += w;
// heap-lize
while(next < l)
{
if(next + 1 < l && h[next] > h[next + 1]) next ++;
if(j > h[next])
&n......