自动搬运

查看原文

来自洛谷，原作者为

	ZJle 人性的弱点,基因的缺陷

搬运于2025-08-24 22:52:11，当前版本为作者最后更新于2023-11-09 19:43:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们将所有的 $a,b$ 递增排序。

首先我们可以知道我们把每个人和对应的手抓饭在圆盘上连线，那么这些连线是不会相交的。

则因为有结构推论,所以若 $a_i$ 与 $b_j$ 相配,则 $a_i+k$ 一定与 $b_j+k$ 相配。

因为人数很少,所以我们直接枚举 $a_1$ 与哪盘饭匹配,然后就得到了 $n$ 个对。

先假设每个对都在顺时针旋转,得到需要旋转的距离 $syf_i=a_i-b_j$ 。

显然,其可以顺时针旋转 $syf_i$ ,亦可以逆时针旋转 $m-syf_i$ 得到。

可以发现,最终结果,一定是对小的 $syf_i$ 顺时针,大的 $syf_i$ 逆时针。

于是我们对 $d_i$ 排序后,枚举哪一半顺时针即可。

时间复杂度 $O(n^2 \log n)$

码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int T, a[N], b[N], n, k, maxn;
pair<int, int> syf[N];
#define fi first
#define se second
int ans=0x3f3f3f3f3f;
void solve()
{
    cin>> n >> k;
    for (int i = 1; i <= k; i++) cin>> a[i];
    for (int i = 1; i <= k; i++) cin>> b[i];
    sort(a + 1, a + k + 1);
    sort(b + 1, b + k + 1);
    ans=0x3f3f3f3f3f3f;
    for (int i = 1; i <= k; i++)
    {
        memset(syf, 0, sizeof(syf));
        for (int j = 1; j <= k; j++)
        {
            syf[j].fi= (a[j] + n - b[(j + i - 1) % k + 1]) % n;
            syf[j].se = (b[(j + i - 1) % k + 1] + n - a[j]) % n;
        }
        sort(syf + 1, syf + k + 1);
        maxn = 0;
        for (int j = k; j >= 0; j--)
        {
            ans = min(ans, syf[j].fi + maxn + min(syf[j].fi, maxn));
            maxn = max(maxn, syf[j].se);
        }
    }
    cout << ans << '\n';
}
auto main() -> signed
{
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}