Traffic Lights

题目描述

The main street of Berland’s capital is a segment with length $s$. The main street has traffic lights installed along it. The traffic lights have been functioning since time immemorial, cyclically changing colors from red to green and vice versa. Each traffic light can be described by four numbers $x_i, r_i, g_i, d_i$, which stand for:

• $x_i$ - the distance from the beginning of the street to the traffic light ($1 \le x_i \lt s$),
• $r_i$ - the duration of the red light illumination ($10 \le r_i \le 20$),
• $g_i$ - the duration of the green light illumination ($10 \le g_i \le 20$),
• $d_i$ - the minimum non-negative moment of time when the traffic light changes the light from green to red ($0 \le d_i \lt r_i+g_i$).

Each traffic light retains its light cycle from the ancient past.

The King of Berland asked the transport minister to customize the traffic lights according to a “green wave” principle. That means that if you start driving from the beginning of the street at the recommended speed, you can drive through the entire street without stopping, that is, you pass each traffic light when it has the green light on.

Now it is time to show the “green wave” to the King, but the work is not even started yet. You may assume that the King starts driving at the moment of time $0$ from the beginning of the street. So the minister decided to choose some speed $v_0$ and tell the king that the “green wave” works specifically for this speed. Moreover, they can switch any number of traffic lights to the “always green” mode. The minister’ aim is to ensure that if the King drives through the street at the recommended speed $v_0$ he encounters no red traffic light. Driving exactly at the moment when the colors are changed is not considered driving through the red light.

Any transport’s maximum speed is limited in Berland: it should not exceed $v_{\max}$. On the other hand, the King will be angry if the recommended speed is less than $v_{\min}$. Thus, the minister should choose such value of $v_0$, which satisfies the inequation $v_{\min} \le v_0 \le v_{\max}$.

Help the minister to find such $v_0$ value, that the number of traffic lights to switch to the “always green” mode is minimum. If $v_0$ is not uniquely defined, choose the maximum possible value of $v_0$.

题意概述

一条长为$s$的公路上有$n$个红绿灯。第$i$个红绿灯在距离起点$x_i$的位置上，周期是$r_i$单位时间红灯加$g_i$单位时间绿灯，第一次从绿灯变成红灯的时刻是$d_i$。一辆车以速度$v_0$从起点开到终点，途中不能停顿。求在$v_{\min} \le v_0 \le v_{\max}$且闯过的红灯数最少的情况下，$v_0$的最大值。

数据范围：$1 \le n \lt 20000, \ 1 \le s \le 20000, \ 10 \le v_{\min} \le v_{\max} \le 50$。

算法分析

把速度看成数轴，那么每个红绿灯可以对应到数轴上的若干个区间——即若$v_0 \in [l, r]$，则经过这个红绿灯时闯了红灯。

由于题目的特殊限制（$10 \le r_i, g_i \le 20, \ 10 \le v_{\min} \le v_0 \le v_{\max} \le 50$），这样的区间不会太多，可以把它们都求出来。问题转化成求数轴上一个点使得覆盖它的区间数最少。离散化后模拟即可。

代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 20005;
static double const EPS = 1e-12;

int pm(double const &n) {
  return fabs(n) < EPS ? 0 : n < 0 ? -1 : 1;
}

std::bitset<N> ans, cur;
struct Query {
  int id, op;
  double x;
  friend bool operator<(Query const &a, Query const &b) {
    return pm(a.x - b.x) ? !~pm(a.x - b.x) : a.op < b.op;
  }
} itv[N * 100];

int main() {
  int n, s, vmn, vmx, top = 0;
  scanf("%d%d%d%d", &n, &s, &vmn, &vmx);
  for (int i = 0, x, r, g, d; i < n; ++i) {
    scanf("%d%d%d%d", &x, &r, &g, &d);
    if (d > g) {
      double l = 1. * x / (d - g);
      itv[top++] = (Query){i, 1, l};
    }
    for (;; d += r + g) {
      double l = 1. * x / (d + r), r = d ? 1. * x / d : 1e9;
      if (pm(r - vmn) < 1) {
        break;
      }
      if (pm(vmx - l) < 1) {
        continue;
      }
      itv[top++] = (Query){i, 1, l}, itv[top++] = (Query){i, -1, r};
    }
  }
  itv[top++] = (Query){n, 1, 0. + vmx};
  std::sort(itv, itv + top);
  int ac = n, cc = 0;
  double vc = 0;
  for (int i = 0; i < n; ++i) {
    ans.set(i);
  }
  for (int i = 0; i < top && pm(itv[i].x - vmx) < 1; ++i) {
    if (itv[i].op == 1) {
      if (cc <= ac && pm(vmn - itv[i].x) < 1) {
        ans = cur, ac = cc, vc = itv[i].x;
      }
      if (itv[i].id < n) {
        cur.set(itv[i].id), ++cc;
      }
    } else {
      cur.reset(itv[i].id), --cc;
    }
  }
  printf("%.10lf\n%d\n", vc, ac);
  for (int i = 0; i < n; ++i) {
    if (ans.test(i)) {
      printf("%d ", i + 1);
    }
  }
  puts("");
  return 0;
}