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])  {   h[cur] = h[next];   cur = next;   next = cur * 2 + 1;  }  else break; } h[cur] = j;} int main(){ freopen("in.txt", "r", stdin); while(init()) {  int i;  for(i = 0; i < t; i ++) push();  printf("%d\n", ans + s); } return 0;}  

评论