The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——A. Ants on a Ring（这种题目就是推性质）（这个环，一定要想办法化曲为直！一定要在一个地方，把环变成一条直线）

题目大意

题目描述
在一个圆上有 $N$ 只蚂蚁。圆被顺时针划分为 $L$ 个位置，编号为 $1$ 到 $L$，其中位置 $L$ 与位置 $1$ 相邻。
每只蚂蚁初始站在不同的位置上，并且都需要到达各自不同的目标位置。
在每一秒内，每只蚂蚁可以选择：

• 停留在原地。

• 顺时针或逆时针移动到相邻的位置。

在任何时刻（包括在两个位置之间移动的过程中），任意两只蚂蚁都不能处于同一个位置。例如，如果某只蚂蚁在某一秒内顺时针从位置 $1$ 移动到位置 $2$，那么在同一秒内，其他蚂蚁不能进行以下操作：

• 停留在位置 $2$（这会导致两只蚂蚁在位置 $2$ 相遇）。

• 逆时针从位置 $3$ 移动到位置 $2$（这会导致两只蚂蚁在位置 $2$ 相遇）。

• 逆时针从位置 $2$ 移动到位置 $1$（这会导致两只蚂蚁在位置 $1$ 和位置 $2$ 之间相遇）。

你需要判断是否有可能让所有蚂蚁都到达各自的目标位置。如果可以，求出所需的最短时间（秒数）。

输入格式
第一行包含两个整数 $N$（$1 \le N \le 1000$）和 $L$（$1 \le L \le 10^9$），分别表示蚂蚁的数量和位置的总数。
第二行包含 $N$ 个互不相同的整数 $A_1, A_2, \dots, A_N$（$1 \le A_i \le L$），表示每只蚂蚁的初始位置。
第三行包含 $N$ 个互不相同的整数 $B_1, B_2, \dots, B_N$（$1 \le B_i \le L$），表示每只蚂蚁的目标位置。

输出格式
输出一行，包含一个整数，表示所有蚂蚁到达目标位置所需的最短时间。如果无论如何都无法全部到达目标位置，则输出星号 *。

样例展示与解释

样例 1
输入：

2 2
2 1
2 1

输出：

0

样例 1 解释：两只蚂蚁初始就已经在各自的目标位置上，因此需要 $0$ 秒。

样例 2
输入：

2 2
1 2
2 1

输出：

1

样例 2 解释：两只蚂蚁可以同时顺时针（或同时逆时针）移动，仅需 $1$ 秒即可到达目标位置。

样例 3
输入：

1 10
1
7

输出：

4

样例 4
输入：

3 5
1 3 2
5 2 4

输出：

*

样例 5
输入：

3 5
1 3 2
4 2 5

输出：

2

样例 5 解释：三只蚂蚁都可以选择逆时针移动，其中第二只蚂蚁需要在中途停留一秒。

思路讲解

这道题目，实际上可以 $O(n)$ 解决（忽略了快排的时间复杂度），至少我们的做法是这个时间复杂度的。

sort(all(lr_global));
for (int i = 0; i < SZ(lr_global); ++i) {
    if (lr_global[0].r > lr_global[i].r) {
        lr_global[i].r += L;
    }
}
auto check = [&]() -> bool {
    for (int i = 1; i < N; ++i) {
        if (lr_global[i].l == lr_global[i - 1].l) {
            return false;
        }
    }
    for (int i = 1; i < N; ++i) {
        if (lr_global[i].r <= lr_global[i - 1].r) {
            return false;
        }
    }
    return true;
};
if (!check()) {
    cout << "*\n";
    return;
}

核心代码就这一段，只能说化曲为直 yyds。

for (ll shift: {-1, 0, 1}) {
    ll ans = 0;
    for (auto [l,r]: lr_global) {
        ans = max(abs(l + L * shift - r), ans);
    }
    ans_global = min(ans_global, ans);
}

为什么这个代码对呢？其实在化曲为直下，一切都非常简单。

说白了，我们只要 l 的相对位置不变，r 的相对位置不变，那么就一定有解，是不是？

那么，我们知道，一个点，他切换方向，其实就是 l 在化曲为直的线段上，平移了 Len 位。如果其他点不也平移的 L 位的话，这个一定会导致错误的发生（即 l 的相对位置发生变化）！

那么我们就知道了，要切换方向，要么一起切换，要么一起不切换。

当然，你会说，这很奇怪啊，明明这个有些例子是有些点逆时针，有些点顺时针啊？其实，这个是因为为了符合我们的第一个条件，就是起始点和结束点必须都保持升序的条件，在保持这个条件的情况下，其实方向的变化是一起的。

AC代码

AC
http://codeforces.com/gym/106416/submission/368041079

源代码

/**
 * Problem: A. Ants on a Ring
 * Contest: The 2026 ICPC Latin America Championship
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106416/problem/A
 * Created: 2026-03-24 19:13:11
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
struct L_R {
    ll l, r;

    bool operator<(const L_R &o) const {
        return l < o.l;
    }
};

void Solve() {
    ll N, L;
    cin >> N >> L;
    vector<L_R> lr_global(N);
    for (int i = 0; i < N; ++i) cin >> lr_global[i].l;
    for (int i = 0; i < N; ++i) cin >> lr_global[i].r;
    // auto lr_backup = lr_global;
    sort(all(lr_global));
    for (int i = 0; i < SZ(lr_global); ++i) {
        if (lr_global[0].r > lr_global[i].r) {
            lr_global[i].r += L;
        }
    }
    auto check = [&]() -> bool {
        for (int i = 1; i < N; ++i) {
            if (lr_global[i].l == lr_global[i - 1].l) {
                return false;
            }
        }
        for (int i = 1; i < N; ++i) {
            if (lr_global[i].r <= lr_global[i - 1].r) {
                return false;
            }
        }
        return true;
    };
    if (!check()) {
        cout << "*\n";
        return;
    }
    ll ans_global = INF;
    for (ll shift: {-1, 0, 1}) {
        ll ans = 0;
        for (auto [l,r]: lr_global) {
            ans = max(abs(l + L * shift - r), ans);
        }
        ans_global = min(ans_global, ans);
    }
    cout << ans_global << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve();
    return 0;
}

/*
AC
http://codeforces.com/gym/106416/submission/368041079

*/

心路历程（WA，TLE，MLE……）