P1678 烦恼的高考志愿题解

ERoRaIn · 2022-10-21 20:01:57 · 题解

看了几个别人的题解，发现没有双指针的，想发一条。~~蒟蒻的第一篇题解，望通过~~。

题目大意

这题的题意挺明显的，就是给一个序列 a 和另一个序列 b ，找出序列 b 中每个元素在 a 中最相近的元素，并求出它们的差值的和。

二分思路

先 sort 一遍 a 序列，对于 b 序列中的每个值都运用二分查找找到 a 中最相近的值，进行统计。易得具体时间复杂度约为 O(nlogn+mlogn)，是本题基本上的最优解。但是由于它主片段的复杂度较大，和排序预处理差不多，这就导致如果在某些输入数据有序并且较大的题目下容易TLE。这里便介绍另一种方法——双指针。

双指针思路

双指针和二分的比较

相比于二分的时间复杂度，双指针的时间复杂度约为 O(nlogn+mlogm) (要 sort 两遍），时间复杂度差不多。而且双指针在实现方面比二分简单许多~~前提是你不会 stl~~。双指针的复杂度主要卡在一开始的排序，而在主要的计算片段，双指针的复杂度为 O(n+m) ，是一种对于有序数据不错的方法。

如何使用双指针

先用 sort 得到两个升序序列 a 和 b ，然后使用两个指针 i , j 分别指向 a , b 中的元素。对于每一个循环中的 a[i] 和 b[j] ，若前者大于后者，显然 a 序列的后面不会有更接近 b[j] 的元素了，可以将答案累加，由于序列 a , b 的单调性，重置临时答案为 b[j+1]-a[i-1] 。若后者大于前者，更新临时答案和 b[j]-a[i] 进行比较。具体特殊情况的判断可以参见代码，这里不好做阐述。

这种方法跑的还是挺快的，虽然在本题没有达到最优解，但 104ms 的时间已经比题解区基本上的题解都要快了

实现代码

实现还是挺简单的，最好是自己先去打一下，下面的代码仅作参考。

#include<cstdio>
#include<cctype>
#include<algorithm>
#define INF 0x3F3F3F3F
#define For(i, j, k) for (register int i(j); i <= k; ++ i)
#define Rof(i, j, k) for (register int i(j); i >= k; -- i)
using namespace std;

inline int _min(int a, int b){return (a >= b) ? b : a;}
inline int read()
{
        int x = 0, f = 1; char c = getchar();
        while (!isdigit(c)){if (c == '-') f = -1; c = getchar();}
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
        x *= f; return x;
}
inline void write(long long x)
{
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + 48);
}

const int MAXN = 1000005;
int m, n;
int a[MAXN], b[MAXN];
int ans = INF;//循环中对于每个b[j] 
long long tot;//累计答案 

signed main()
{
        m = read(); n = read();
        For(i, 1, m) a[i] = read();
        For(i, 1, n) b[i] = read();

        a[0] = ~INF;//因为后面代码中要和a[0]进行相减取min，故设为最大 

        sort (a + 1, a + m + 1);
        sort (b + 1, b + n + 1);

        for (register int i(1), j(1); i <= m, j <= n;)
                if (a[i] >= b[j]) 
                        tot += _min(ans, a[i] - b[j]), ++ j, ans = b[j] - a[i - 1];//累计答案，增加j指针，更新临时答案 
                else
                {
                        ans = _min(ans, b[j] - a[i]);
                        if (i == m) tot += ans, ++ j, ans = b[j] - a[i];//若i已经指向最后一个了，后面的学生只能和a[i]进行求差 
                        else ++ i;//a[i]不是最后一个，则求第一个大于等于b[j]的学校 
                }

        write(tot);
        return 0;
}