HDU4393 - 扔钉子

题设

【问题描述】

年度学校自行车比赛开始了，ZL是这所学校的学生，他太无聊了，因为他不能骑自行车！因此，他决定干预比赛，他通过以前的比赛视频获得了选手的信息，一个选手第一秒可以跑F米，然后每秒跑S米。每个选手有一条直线跑道，ZL每秒向跑的最远的运动员跑道扔一个钉子，在自行车胎爆炸之后，该选手将被淘汰。如果有多个选手是NO.1，则他总是选择ID最小的选手扔钉子。

【输入形式】

每个测试用例的第一行包含一个整数n（1≤n≤50000），表示选手人数，然后跟随n行，每行包含第i个选手的两个整数Fi（0≤Fi≤500），Si（0<Si≤100），表示该选手第一秒可以跑Fi米，然后每秒跑Si米，i是玩家从1开始的ID。

【输出形式】

输出n个数字，以空格分隔，第i个数字是选手的ID，该选手将在第i秒结束时被淘汰。

【样例输入】

3

100 1

100 2

3 100

【样例输出】

1 3 2

题解

因为本题中的F和S似乎没有主导性，作者采用了链表的方式进行模拟，通过数组来构建了链表，但此法显然速度较慢，时间复杂度为O(n²)，只能应付数据较少的情况，通过学校oj平台的测试没有问题。

#include <cstdio>
const int maxn = 50000 + 10;
int lc[maxn], rc[maxn];
int p[maxn], speed[maxn];
int head;

int main() {
  // freopen("in.txt", "r", stdin);
  int n;
  head = 1;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int f, s;
    scanf("%d %d", &f, &s);
    p[i] = f;
    speed[i] = s;
    rc[i] = i + 1;
    lc[i + 1] = i;
    if (i == 1) {
      lc[i] = -1;
    }
    if (i == n) {
      rc[i] = -1;
    }
  }
  while (1) {
    int k = head, max_p = head;
    while (k > 0) {
      if (p[k] > p[max_p]) {
        max_p = k;
      }
      k = rc[k];
    }
    printf("%d ", max_p);
    if (lc[max_p] < 0 && rc[max_p] < 0) break;
    if (lc[max_p] < 0) {
      head = rc[max_p];
      lc[rc[max_p]] = -1;
    } else if (rc[max_p] < 0) {
      rc[lc[max_p]] = rc[max_p];
    } else {
      rc[lc[max_p]] = rc[max_p];
      lc[rc[max_p]] = lc[max_p];
    }
    k = head;
    while (k > 0) {
      p[k] += speed[k];
      k = rc[k];
    }
  }
}