The 2026 ICPC Latin America Championship(2026 拉丁美洲决赛)-Gym-106416——A. Ants on a Ring(这种题目就是推性质)(这个环,一定要想办法化曲为直!一定要在一个地方,把环变成一条直线) · znzryb
## 题目大意
**题目描述**
在一个圆上有 $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)$ 解决(忽略了快排的时间复杂度),至少我们的做法是这个时间复杂度的。
```cpp
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。
```cpp
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](http://codeforces.com/gym/106416/submission/368041079)
::: 源代码
```cpp
/**
* 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……)