或许前路永夜,即便如此我也要前进,因为星光即便微弱也会为我照亮前路。

【题目概括】

在一个线性道路上除了起点和终点一共有n个点,给出n+1个路段的长度w_i,以及在每一个路口的红绿灯的周期,所有红绿灯的周期是相同的,绿灯持续时间为g,红灯持续时间为r
车在过路口的时候,如果是红灯就会被拦下来,直到下一个绿灯。
现在给定m个车出发的时间t_i,求出到达终点的最短时间。

【思路要点】

  • 对于所有的红绿灯的周期都是相同的,所以我们可以将问题划分为两个子问题:被第一个红绿灯拦住之前、拦住之后。
  • 第一个子任务:
  • 我们记录前缀和方便计算两两之间的距离,sum[i]=\sum^{i}_{j=1}w_j
  • 那么被第i红绿灯拦住的充要条件:(t_s+sum[i])\bmod (g+r)>g。(原本在第g秒是可以过红绿灯的,但是从零开始标号的时间在第g秒就被拦住了)
  • 我们用权值线段树维护最小编号,将原式展开后得到了(t_s\bmod (g+r)+sum[i]\bmod (g+r))\bmod (g+r)
  • 可以将这个情况分成两种情况讨论,如果t_s\leq g,那么加上sum[i]\mod (g+r)也不可能超过g,所以这样只有一段答案区间[g-t_s,mod-1-t_s]
  • 否则有两段区间分别为[0,mod-1-t_s][mod-(t_s-(g-1))+1,mod-1]
  • 第二个子任务我们可以通过DP求解。
  • g[i]表示从第i个路灯的绿灯开始到终点的最短时间。
  • 转移方程为:g[i]=g[j]+dis(i,j)+(g+r-dis(i,j)\bmod (g+r))
  • 其中ji后第一个被拦住的红绿灯。
  • 我们也用类似于上面的做法,从后向前DP,用权值线段树优化DP,也就是固定sum[i]\bmod (g+r),然后查找答案区间最小的j。(本质就是向后数个数)
  • 其实就是两个sum[i]\bmod (g+r)sum[j]\bmod (g+r)在线段树上的距离\ge g,转化成严格>g-1,这样我们就只需要求出我们不需要的区间.
  • 如果sum[i]\bmod (g+r)-1<(g+r)-1也就说明不需要的区间是一段连续的区间:[sum[i]\bmod (g+r),sum[i]\bmod (g+r)+g-1],那么查询的答案区间就被分成了两段[sum[i]\bmod (g+r)+g,mod-1][0,sum[i]\bmod (g+r)-1]
  • 否则不需要的区间就变成了两段,我们查询区间就变成了一段[(sum[i]\bmod (g+r)+g-1)\bmod (g+r)+1,(sum[i]\bmod (g+r)-1]
  • 时间复杂度 \mathcal{O}(m\times log(g+r))

【代码】

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

template <typename T> void chkmax(T& x, T y) { x = x > y ? x : y; }
template <typename T> void chkmin(T& x, T y) { x = x < y ? x : y; }

const int N = 2e5 + 5;
ll w[N], sum[N], dp[N];
int n, g, r;
ll mod;

ll getDis(int i, int j) {
  if (i > j)
    return 0;
  return sum[j] - sum[i];
}

#define lc (tr[nod].ch[0])
#define rc (tr[nod].ch[1])

struct Node {
  int ch[2];
  ll val;
} tr[N * 32];

int root, tot = 0;

void pushup(int nod) {
  tr[nod].val = INF;
  if (lc) 
    chkmin(tr[nod].val, tr[lc].val);
  if (rc)
    chkmin(tr[nod].val, tr[rc].val);
}

void insert(int& nod, ll l, ll r, ll k, int v) {
  if (!nod)
     tr[nod = ++tot].val = INF;
  if (l == r) {
    tr[nod].val = v;
    return;
  }
  ll mid = (l + r) >> 1;
  if (k <= mid) 
    insert(lc, l, mid, k, v);
  else 
    insert(rc, mid + 1, r, k, v);
  pushup(nod);
}

ll query(int nod, ll l, ll r, ll ql, ll qr) {
  if (!nod)
    return INF;
  if (ql <= l && r <= qr)
    return tr[nod].val;
  ll mid = (l + r) >> 1, res = INF;
  if (ql <= mid)
    chkmin(res, query(lc, l, mid, ql, qr));
  if (qr > mid)
    chkmin(res, query(rc, mid + 1, r, ql, qr));
  return res;
}

ll queryPos1(ll sumi) {
  sumi %= mod;
  ll res = INF;
  if (sumi + g - 1 < mod - 1) {
    ll t1 = query(root, 0, mod - 1, sumi + g, mod - 1);
    ll t2 = query(root, 0, mod - 1, 0, sumi - 1);
    chkmin(res, t1), chkmin(res, t2);
  }
  else 
    chkmin(res, query(root, 0, mod - 1, (sumi + g - 1) % mod + 1, sumi - 1));
  return res;
}

ll queryPos2(ll t0) {
  t0 %= mod;
  ll res = INF;
  if (t0 <= g)
    chkmin(res, query(root, 0, mod - 1, g - t0, mod - 1 - t0));
  else {
    chkmin(res, query(root, 0, mod - 1, 0, mod - 1 - t0));
    chkmin(res, query(root, 0, mod - 1, mod - (t0 - (g - 1)) + 1, mod - 1));
  } 
  return res;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> g >> r;
  mod = g + r;
  for (int i = 1; i <= n + 1; i++) 
    cin >> w[i];
  sum[0] = 0;
  for (int i = 1; i <= n + 1; i++)
    sum[i] = sum[i - 1] + w[i];
  dp[n + 1] = w[n + 1];
  for (int i = n; i >= 1; i--) {
    ll pos = queryPos1(sum[i]);
    if (pos == INF)
      dp[i] = getDis(i, n + 1);
    else {
      ll Dis = getDis(i, pos);
      dp[i] = dp[pos] + Dis + (mod - Dis % mod);
    }
    insert(root, 0, mod - 1, sum[i] % mod, i);
  }
  int q; cin >> q;
  while (q--) {
    int t0; cin >> t0;
    ll pos = queryPos2(t0);
    if (pos == INF)
      cout << t0 + sum[n + 1] << '\n';
    else {
      ll tmp = getDis(0, pos);
      cout << t0 + tmp + (mod - (t0 + tmp) % mod) + dp[pos] << '\n';
    }
  }
  return 0;
}

【类型】校内训练 【类型】做题记录 【算法】动态规划 【算法】线段树

【模板题】康托展开
上一篇 «
None
» 下一篇