507

# 题目

In airport of Bytetown, there are two long queues waiting for security check. Checking a person needs one minute, and two queues can be checked at the same time.

Two teams $A$ and $B$ are going to travel by plane. Each team has $n$ players, ranked from $1$ to $n$ according to their average performance. No two players in the same team share the same rank. Team $A$ is waiting in queue $1$ while team $B$ is waiting in queue $2$. Nobody else is waiting for security check.

Little Q is the policeman who manages two queues. Every time he can check one person from one queue, or check one each person from both queues at the same time. He can't change the order of the queue, because that will make someone unhappy. Besides, if two players $Ai$ and $Bj$ are being checked at the same time, satisfying $|Ai-Bj|leq k$, they will make a lot of noise because their rank are almost the same. Little Q should never let that happen.

Please write a program to help Little Q find the best way costing the minimum time.

The first line of the input contains an integer $T(1leq Tleq15)$, denoting the number of test cases.

In each test case, there are $2$ integers $n,k(1leq nleq 60000,1leq kleq 10)$ in the first line, denoting the number of players in a team and the parameter $k$.

In the next line, there are $n$ distinct integers $A1,A2,...,An(1leq Aileq n)$, denoting the queue $1$ from front to rear.

Then in the next line, there are $n$ distinct integers $B1,B2,...,Bn(1leq Bileq n)$, denoting the queue $2$ from front to rear.

For each test case, print a single line containing an integer, denoting the minimum time to check all people.

1
4 2
2 3 1 4
1 2 4 3

7

# 题解

## 暴力思路

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

k 又是一个非常小的数字

(这里 +k 是为了保证为正数)

## 题解的思路

(i,j)表示第一队第i个人和第二队第j个人,当发现他们的差值大于k

lower_bound() 找的是第一个小于等于的位置,与我们的要求不符

# 代码

## 暴力思路

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 60005;
const int maxk = 11;

int queue_a[maxn], queue_b[maxn];
int DP[maxn][maxk << 2];
int n, k;

void init() { memset(DP, -1, sizeof(DP)); }

int dfs(int apos, int bpos) {
int RETURN = -1;
if (!apos || !bpos) {
RETURN = apos | bpos;
} else {
if (abs(queue_a[apos] - queue_b[bpos]) <= k) {
//暴力
int &dp = DP[apos][queue_a[apos] - queue_b[bpos] + k];
if (dp == -1)
dp = min(dfs(apos - 1, bpos), dfs(apos, bpos - 1)) + 1;
RETURN = dp;
} else {
RETURN = dfs(apos - 1, bpos - 1) + 1;
}
}
return RETURN;
}

int main() {
// freopen("out.txt", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);

init();
for (int i = 1; i <= n; i++)
scanf("%d", &queue_a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &queue_b[i]);

printf("%d\n", dfs(n, n));
}
return 0;
}

## 题解思路

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 60005;
const int maxk = 15;

int queue_a[maxn], queue_b[maxn];
int bposList[maxn];

int DP[maxn][maxk << 2];
vector<int> DisList[maxn << 2];

int n, k;

bool cmp(int a, int b) { return a > b; }

void init() {
memset(DP, -1, sizeof(DP));
for (int i = 0; i <= n << 2; ++i)
DisList[i].clear();
}

int dfs(int apos, int bpos, int deep) {
int RETURN = -1;
if (!apos || !bpos) {
RETURN = apos | bpos;
} else {
if (abs(queue_a[apos] - queue_b[bpos]) <= k) {
//暴力
int &dp = DP[apos][queue_a[apos] - queue_b[bpos] + k];
if (dp == -1) {
dp = min(dfs(apos - 1, bpos, deep + 1),
dfs(apos, bpos - 1, deep + 1)) +
1;
}
RETURN = dp;
} else {
int dis = apos - bpos + n;
vector<int> &List = DisList[dis];
vector<int>::iterator it =
lower_bound(List.begin(), List.end(), apos, cmp);
if (it == List.end() || *it == apos) {
RETURN = max(apos, bpos);
} else {
int lastapos = *it;
RETURN = dfs(lastapos, bpos - apos + lastapos, deep + 1) +
apos - lastapos;
}
}
}
return RETURN;
}

int max(int a, int b) { return a > b ? a : b; }

int main() {
// freopen("out.txt", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);

init();
for (int i = 1; i <= n; i++)
scanf("%d", &queue_a[i]);
for (int i = 1; i <= n; i++) {
scanf("%d", &queue_b[i]);
bposList[queue_b[i]] = i;
}

for (int apos = n; apos >= 1; --apos) {
int a = queue_a[apos];
for (int b = a - k; b <= a + k; ++b) {
int bpos = bposList[b];
int dis = apos - bpos + n;
DisList[dis].push_back(apos);
}
}

printf("%d\n", dfs(n, n, 1));
}
return 0;
}

• 点击查看/关闭被识别为广告的评论