RiceArrangement

Wowo is a hospitable Xinjiang uncle. ${k}$ guests will have Uyghur Polo (a traditional Uyghur food) in Wowo's house around a big round table. ${n}$ ( $n\ge k$ ) chairs are placed around the table uniformly. Each guest sits on a chair and no two guests sit on the same chair. ${k}$ bowls of Uyghur Polo are on the table. Each bowl is next to some chair (with or without some guest sitting on it). No two bowls locate at the same position.

As a waiter, you are supposed to assign each person with exactly one bowl of Uyghur Polo. The table can be rotated, so each time you can turn it $\frac{2\pi}{n}$ degrees clockwise or counterclockwise. The bowls turn with the table while the chairs and guests do not move. When one bowl of Uyghur Polo is in front of a guest, he can either take it or wait for another.

You want to minimize the total times of table rotating so that everybody can have meals as quickly as possible.

(Formal definition: 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,\ldots, 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) \bmod 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) \bmod n$ after the rotation. ( $x\bmod 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}$ .

#include<bits/stdc++.h> using namespace std; const int maxn=1005; int T,n,m,ans; int a[maxn],b[maxn],c[maxn]; int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); ans=n; for(int i=0;i<m;i++)scanf("%d",&a[i]); for(int i=0;i<m;i++)scanf("%d",&b[i]); sort(a,a+m); sort(b,b+m); for(int i=0;i<m;i++){ for(int j=0;j<m;j++)c[j]=(b[(i+j)%m]-a[j]+n)%n; sort(c,c+m); ans=min(ans,min(c[m-1],n-c[0])); for(int j=0;j<m-1;j++) ans=min(ans,c[j]+n-c[j+1]+min(c[j],n-c[j+1])); } printf("%d\n",ans); } return 0; }

详情