二路归并 · 双指针 是一种优化思想。它可以在 \(O(n)\) 的复杂度下把两个长度为 \(n\) 的有序数组合并为一个有序数组。
它的具体处理方法如下：
定义两个长度为 \(n\) 的升序数组 \(a,b\)。，合并完后长度为 \(2n\) 的数组 \(c\)，初始化两个指针 \(x=y=1\)（这里数组下标从 \(1\) 开始）
-
如果 \(a_x < b_y\)，则 \(c_{cnt++}=a_x\)，同时 \(x++\)。
-
如果 \(a_x > b_y\)，则 \(c_{cnt++}=b_y\)，同时 \(y++\)
正确性显然，由于我们确保 \(a,b\) 数组升序，故如果 \(a_x < b_y\) ，则 \(b\) 数组从 \(y\) 以后的数一定大于 \(a_x\)，所以按照顺序取 \(a_x\)，同时移动 \(x++\)。
对于 \(a_x > b_y\) 同理。
由此可见，对于把一个长度为 \(n\) 的数组排序，我们可以分治，然后不断二路归并。这就是归并排序。
双指针思想应用广泛，接下来我们给出几个例题。
例题 · Luogu P1309 瑞士轮
经典永流传之瑞士轮。后面好多题目都用到了类似于瑞士轮的思想。
我们发现每轮比赛都需要进行结构体排序，本题的复杂度显然无法接受。
注意到每轮比赛后胜利和失败是唯一的，不妨记录每轮比赛后胜利和失败的人，由于我们一开始确保数组有序，所以胜利和失败的人分数一定是单调递增的，可以二路归并。
实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 10010
using namespace std;
int n, m, k;
int s[N], w[N], q[N], q0[N], q1[N];
bool cmp(int a, int b)
{
if (s[a] != s[b])
return s[a] > s[b];
return a < b;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n * 2; i++)
scanf("%d", &s[i]);
for (int i = 0; i < n * 2; i++)
scanf("%d", &w[i]);
for (int i = 0; i < n * 2; i++)
q[i] = i;
sort(q, q + n * 2, cmp);
while (m--)
{
int t0 = 0, t1 = 0;
for (int i = 0; i < n * 2; i += 2)
{
int a = q[i], b = q[i + 1];
if (w[a] < w[b])
{
s[b]++;
q0[t0++] = a;
q1[t1++] = b;
}
else
{
s[a]++;
q0[t0++] = b;
q1[t1++] = a;
}
}
int i = 0, j = 0, t = 0;
while (i < t0 && j < t1)
if (cmp(q0[i], q1[j]))
q[t++] = q0[i++];
else
q[t++] = q1[j++];
while (i < t0)
q[t++] = q0[i++];
while (j < t1)
q[t++] = q1[j++];
}
printf("%d\n", q[k - 1] + 1);
}