526互联

Educational Codeforces Round 158 (Rated for Div. 2)

发布时间 2023-11-28 23:31:30作者: Howardlhhhr

A. Line Trip

There is a road, which can be represented as a number line. You are located in the point \(0\) of the number line, and you want to travel from the point \(0\) to the point \(x\), and back to the point \(0\).

You travel by car, which spends \(1\) liter of gasoline per \(1\) unit of distance travelled. When you start at the point \(0\), your car is fully fueled (its gas tank contains the maximum possible amount of fuel).

There are \(n\) gas stations, located in points \(a_1, a_2, \dots, a_n\). When you arrive at a gas station, you fully refuel your car. Note that you can refuel only at gas stations, and there are no gas stations in points \(0\) and \(x\).

You have to calculate the minimum possible volume of the gas tank in your car (in liters) that will allow you to travel from the point \(0\) to the point \(x\) and back to the point \(0\).

Input

The first line contains one integer \(t\) (\(1 \le t \le 1000\)) — the number of test cases.

Each test case consists of two lines:

  • the first line contains two integers \(n\) and \(x\) (\(1 \le n \le 50\); \(2 \le x \le 100\));
  • the second line contains \(n\) integers \(a_1, a_2, \dots, a_n\).

Output

For each test case, print one integer — the minimum possible volume of the gas tank in your car that will allow you to travel from the point \(0\) to the point \(x\) and back.

翻译:

有一条路，可以用一条数线来表示。你位于数线上的点 \(0\) ，你想从点 \(0\) 到点 \(x\) ，再回到点 \(0\) 。

你乘汽车旅行，每行驶 \(1\) 个单位的距离要花费 \(1\) 升汽油。当您从点 \(0\) 出发时，汽车已加满油（油箱中的油量已达到最大值）。

在 \(a_1, a_2, \dots, a_n\) 点有 \(n\) 个加油站。到达加油站后，为汽车加满油。注意只能在加油站加油， \(0\) 和 \(x\) 点没有加油站。

你必须计算出你的汽车油箱的最小容积（以升为单位），这样你才能从点 \(0\) 行驶到点 \(x\) 并返回到点 \(0\)

#include <bits/stdc++.h>
using namespace std;
bool a[1000];
void solve()
{
    memset(a,0,sizeof a);
    int n,x;
    cin >> n >> x;
    int ans = 0,res = 0;
    int last = 0;
    for(int i = 0;i<n;i++)
    {
        int k;
        cin >> k;
        a[k] = true;
        last = max(last,k);
    }
    for(int i = 1;i<=x;i++)
    {
        res++;
        ans = max(res,ans);
        if(a[i])res = 0;
        //cout << res << endl;
    }
    ans = max(ans,(x - last)*2);
    cout << ans << endl;
}
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}