← back to paste›Edit / fork

Untitled paste

#2HWh3m9LLZpublic / publicnew version

anonymous created 21 hours ago Expires in 6 days 1.3 KB syntax: text

Your changes create a new paste linked to this one — the original is untouched.

new version Your changes create a new paste linked to this one — the original is untouched.

Visibility Public feed Access public

Change note (optional)

This paste will be listed on the public feed. Change Visibility if you only want people with the link to see it.

Cancel

#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;
}