题解：B4196 [海淀区小学组 2023] 赛车游戏

· · 题解

感觉自己的做法很奇怪，不过还是过了。

具体来说，就是以双指针表示两辆赛车的位置，搜索离两辆赛车最近的加速带，让到加速带时间更短的赛车（后称为时间短的车，另一辆车称为时间长的车或另一辆车）位置更新到此加速带，另一辆前进相对的距离，直到加速带全部搜索完后再让答案加上两车距离除以两车速度之和，因为没有加速带后两车的速度不会改变，由于会有小数的存在，所以答案和双指针都改为 double 就好了（另外如果不知道 deque 是什么的继续往下看就好了）。

具体代码如下：

//Just Sayori
#include <bits/stdc++.h>
using namespace std;
#define ll long long//定义宏，但这道题没什么用处。
inline ll read()//快读，如果不清楚可以直接 cin 或者 scanf。
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int a;
deque<int> q;//双端队列，用来记录加速带。
int main()
{
    int t = read();
    while (t--)
    {
        int n = read(), m = read();
        for (int i = 1; i <= n; i++) a = read(), q.push_back(a);
        double l = 0, r = m, sl = 1, sr = 1, ans = 0; //记得开 double。
        while (!q.empty())//如果有加速带。
        {
            if ((q.front() - l) * 1.0 / sl <= (r - q.back()) * 1.0 / sr)//判断两辆车到各自最近的加速带的时间。
            {
                r -= (q.front() - l) * 1.0 / sl * sr;//另一辆车移动相应的距离。（时间乘上自身速度）
                ans += (q.front() - l) * 1.0 / sl;//答案增加。
                l = q.front();//时间短的车直接移动到该加速带。
                q.pop_front();//删除加速带。
                sl++;//时间短的车速度增加
            }
            else
            {
                l += (r - q.back()) * 1.0 / sr * sl;
                ans += (r - q.back()) * 1.0 / sr;
                r = q.back();
                q.pop_back();
                sr++;
            }
        }
        ans += (r - l) * 1.0 / (sl + sr) * 1.0;//最后加上两车之距与两车速度和的商。
        printf("%.15lf\n", ans);//输出答案可以直接不加小数位数的输出。
    }
    return 0;
}

另外记得判断的是两车到下一加速带花费的时间，而非距离，另一辆车移动的距离也是时间短的车移动花费的时间乘上时间长的车的速度，答案记录的也是花费的时间，否则如果两车都移动时间短的车到下一加速带的距离，答案增加的也是两车移动距离之和除以速度之和就会只得十分（除了我这样的蒟蒻也没有人会这样写吧） 比如：

while (!q.empty())
{
  if (q.front() - l <= r - q.back())
  {
      r -= (q.front() - l);
      ans += (q.front() - l) * 2.0 / (sl + sr);
      l = q.front();
      q.pop_front();
      sl++;
  }
  else
  {
      l += (r - q.back());
      ans += (r - q.back()) * 2.0 / (sl + sr);
      r = q.back();
      q.pop_back();
      sr++;
  }
}

最近 deque 用多了什么题都在用，这里也可以用数组代替（不过更麻烦？），因为这道题加速带给出的位置是递增的，简单讲解一下：deque 是 C++STL（标准模板库）的一个容器，它允许在两端进行插入和删除操作，功能非常强大，使用它需要包含头文件 include<deque> 当然用万能头就不用担心了，它的用法如下：

//定义：
deque<int> q1;
deque<long long>q2;
deque<double> q3;
deque<string> q4;
//常见函数：
deque<int> q;//先定义。
int x;
q.push_front(x);//在队列头部插入元素。
q.push_back(x);//在队列尾部插入元素。
q.pop_front();//在队列头部删除元素。
q.pop_back();//在队列尾部删除元素。
q.front();//返回队列头部元素。
q.back();//返回队列尾部元素。
q.empty();//如果队列为空，返回 1，否则返回 0。
q.size();//返回队列长度。
//不要像我这样把队列元素删完还让队列返回值，会出事的。

感谢您的观看！