P9826题解

ZJle · 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;
}