2020ICPC上海 H.Rice Arrangement

题目链接

题目描述
The boundary of the table is a circle. $n$ chairs are at $n$ points on the circle whose convex hull is a regular polygon with $n$ vertices. We name the points $0,\dots ,n-1$ in counterclockwise order. The $i$-th bowl is at point $b_i$ ($0\le b_i<n$) initially. The $i$-th guest is at point $a_i$ ($0\le a_i<n$) initially. If you turn the table counterclockwise, the bowl at point $b_i$ ($1\le i\le k$) will be moved to point $(b_i+1)\mathrm{m}\mathrm{o}\mathrm{d}n$ after the rotation. If you turn the table clockwise, the bowl at point $b_i$ ($1\le i\le k$) will be moved to point $(b_i-1)\mathrm{m}\mathrm{o}\mathrm{d}n$ after the rotation. ($x\mathrm{m}\mathrm{o}\mathrm{d}n$ is defined as the smallest nonnegative integer $r$ such that $x-r$ is a multiple of $n$.

输入描述:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n,k$ ($1\le n\le 10^9,1\le k\le \min (n,1000)$) indicating the size of the table and the number of persons and bowls of Uyghur Polo.

In the second line, there are $k$ integers $a_1,a_2,\dots ,a_k$ ($0\le a_i<n$), indicating the positions of the persons. No two guests share the same position.

In the third line, there are $k$ integers $b_1,b_2,\dots ,b_k$ ($0\le b_i<n$), indicating the initial positions of the bowls. No two bowls of Uyghur Polo locate at the same position.

It is guaranteed that the sum of $k$ over all test cases does not exceed $5000$.

输出描述:
For each test case, output the minimal total times of rotations such that each guest can have exactly one bowl of Uyghur Polo.
示例1
输入

1
4 2
0 3
1 2

输出

2

示例2
输入

1
14 5
0 12 13 8 9
9 2 6 13 5

输出

6

将序列 $a$ 和 $b$ 排序。
记 $c_{i,j}=(a_j-b_{(j+i)\mathrm{m}\mathrm{o}\mathrm{d}k}+n)\mathrm{m}\mathrm{o}\mathrm{d}n$，然后将序列 $c$ 排序。
显然，最优方案最存在于以下两种方案中：

• 第 $j$ 个盘子匹配第 $(j+i)\mathrm{m}\mathrm{o}\mathrm{d}k$ 个盘子，即盘子整体往一个方向旋转。
  答案为两个方向中的最小值，即 $\min (n-c_0,c_{k-1})$ 。
• 盘子整体往一个方向旋转一个角度，再反向旋转一个角度。
  选取 $c$ 中相邻两个值 $c_{j-1},c_j$ ，则答案为 $n-c_j+c_{j-1}+\min (n-c_j,c_{j-1})$ 。
  因为对于距离大于等于 $c_j$ 的匹配，反向旋转 $n-c_j$ 一定能匹配到，另一方向旋转 $c_{j-1}$ 也能匹配到剩余部分，在两次旋转之间另外还要旋转到初始状态，即 $\min (n-c_j,c_{j-1})$ 。显然最方案只能存在于这些情况中。

枚举 $i$ 求解，时间复杂度为 $O(T{k}^2\log k)$ 。

#include<bits/stdc++.h>

using namespace std;
const int N = 1005;
int a[N], b[N], c[N];
int T, n, k;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 0; i < k; i++)scanf("%d", &a[i]);
        for (int i = 0; i < k; i++)scanf("%d", &b[i]);
        sort(a, a + k), sort(b, b + k);
        int ans = n;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++)
                c[j] = (a[j] - b[(j + i) % k] + n) % n;
            sort(c, c + k);
            ans = min(ans, min(c[k - 1], n - c[0]));
            for (int j = 1; j < k; j++)
                ans = min(ans, n - c[j] + c[j - 1] + min(n - c[j], c[j - 1]));
        }
        printf("%dn", ans);
    }
}

最后

以上就是感动雪碧为你收集整理的2020ICPC上海 H.Rice Arrangement的全部内容，希望文章能够帮你解决2020ICPC上海 H.Rice Arrangement所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。