← volver a la publicación›Editar / bifurcar

Publicación sin título

#2HWh3m9LLZpublic / publicnueva versión

anónimo creado 22 hours ago Caduca en 6 days 1.3 KB sintaxis: text

Tus cambios crean una nueva publicación enlazada a esta — la original no se toca.

nueva versión Tus cambios crean una nueva publicación enlazada a esta — la original no se toca.

Visibilidad Feed público Acceso public

Nota de cambio (opcional)

Esta publicación aparecerá en el feed público. Cambia Visibilidad si solo quieres compartirla por enlace.

Cancelar

#include <bits/stdc++.h>
using namespace std;
#define int long long  // 数据范围大，开long long防溢出

int n, L;
vector<int> arr;

signed main() {
    // 快读快写
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin >> n >> L;
    int m = L / 2;  // m是半圆长度，传送的距离

for (int i = 0; i < n; i++) {
        int a; cin >> a;
        // opp是a的正对（传送后）的位置
        int opp = a + m;
        if (opp >= L) opp -= L;
        // 将一对对径点压缩成[0,m)内的代表点，取较小的那个
        arr.push_back(min(a, opp));
    }

sort(arr.begin(), arr.end());
    // 去重：相同压缩点只保留一份
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    int k = arr.size();

// 只有一类点，站原地直接传送就能全部访问，时间0
    if (k == 1) {
        cout << 0 << endl;
        return 0;
    }

int gap = 0;
    // 计算排序后相邻点之间的空隙
    for (int i = 1; i < k; i++) {
        gap = max(gap, arr[i] - arr[i-1]);
    }
    // 环形：最后一个点回到第一个点的空隙
    int ci = m - (arr.back() - arr[0]);
    gap = max(gap, ci);

// m是总长度，减去最大空隙就是最少需要行走的距离
    int ans = m - gap;
    cout << ans << endl;

return 0;
}