2020ICPC上海 H. Rice Arrangement

103 阅读 0 评论 68 点赞

我是靠谱客的博主英勇吐司，这篇文章主要介绍2020ICPC上海 H. Rice Arrangement，现在分享给大家，希望可以做个参考。

2020ICPC上海 H. Rice Arrangement

题意

有一个周长为 $n$ 圆桌，有 $k$ 个人和 $k$ 盘菜，给出 $k$ 个人和 $k$ 盘菜的初始位置，当一个人面前有一盘菜时，可以拿走，也可以再等一碗。问最少旋转多少次，可以把 $k$ 盘菜分给 $k$ 个人。

解法

首先有一个结论，把每个人和他分到的菜连线，不会有交点。

那么可以对人的位置和菜的位置进行排序，然后枚举第一个人分到哪一盘菜，对每种情况取最小答案。

人和菜匹配之后，先计算出菜需要按照顺时针旋转 $c_i$ 度可以到达人的位置。再对 $c_i$ 进行排序，那么可以通过顺时针转 $max(c_i)$ 或者逆时针转 $n-min(c_i)$ ，或者先顺时针再逆时针，或者先逆时针再顺时针，也就是先旋转顺时针 $c_j$ ，那么 $[1, j]$ 的菜都到达了位置，再逆时针旋转 $c_j$ 回到最初的状态，再逆时针旋转 $c_{j+1}$ ，这样 $[j + 1, k]$ 的菜到达了位置，枚举 $j$ 取最小值即可。

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#pragma region
//#pragma optimize("Ofast")
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
#define tr t[root]
#define lson t[root << 1]
#define rson t[root << 1 | 1]
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, a, n) for (int i = n; i >= a; --i)
#pragma endregion
const int maxn = 1e3 + 5;
ll a[maxn], b[maxn], c[maxn];
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, k;
scanf("%d%d", &n, &k);
rep(i, 0, k - 1) scanf("%lld", &a[i]);
rep(i, 0, k - 1) scanf("%lld", &b[i]);
sort(a, a + k);
sort(b, b + k);
ll ans = 1e18;
rep(f, 0, k - 1) {
rep(i, 0, k - 1) c[i] = (b[(i + f) % k] - a[i] + n) % n;
sort(c, c + k);
ans = min({ans, c[k - 1], n - c[0]});
rep(i, 0, k - 2) {
ans = min(ans, 2 * c[i] + (n - c[i + 1]));
ans = min(ans, 2 * (n - c[i + 1]) + c[i]);
}
}
printf("%lldn", ans);
}
}