ABC212

C - Min Difference

题意描述：

给定两段长度分别为n和m的序列A和B，问最小的$|a_{i}-b_{j}|$

是多少？ $1\le i\le n, 1\le j \le m$

收获：

• 对于题目要求，只需要求出最小的值是多少，而不关心取最小值时候的i和j的位置。因此我们对于这种在两个序列中寻找特定数来满足条件的问题，我们最好采取排序来使得问题变得更加清晰
• 排序后我们考虑对于特定的 $a_{i},j'$最小且满足 $a_{i}\le b_{j’} $ ,则对于任意$j>j'$ 都不需要比较
• 同样地，对于$i$来讲，任意$i<i'$的都不需要比较

操作

• 当$a_{i}>b_{j},j++$, 每一次迭代都更新答案
• 当$a_{i}<=b_{j},i++$
• 此时$i$一定满足 $a_{i}\ge b_{j'}$ 令此时的$i=i'$ ,则对于任意$i<i'$ 都不需要比较，所以回到第一步，更新$j'$使得小且满足$a_{i}\le b_{j'}$

代码

#include<bits/stdc++.h>
using namespace std;
int a[200001];
int b[200001];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    int i=1,j=1;
    int ans=1e+9;
    while(i<=n&&j<=m)
    {
        ans=min(ans,abs(a[i]-b[j]));
        if(a[i]>b[j]) j++;
        else if(a[i]<=b[j]) i++;
    }
    cout<<ans<<endl;
    return 0;

}

D - Querying Multiset

题目描述：D - Querying Multiset

集合s初始为空，三种操作：

• 添加一个数$x_{i}$ 到集合$s$中
• 对于集合中的每个元素＋y
• 取出集合中最小的数并输出

思路：注意到y不会影响到集合内部元素的排序，所以考虑堆，再建立变量plus记录直到当前询问的$\sum y_{i}$

• 对于操作一，直接加入堆中
• 对于操作二，plus+=y
• 对于操作三，弹出后加上plus输出

代码：略

E - Safety Journey

题目描述：E - Safety Journey

给定一张图，n个点，m条边，问从1开始，在1结束，长度为k的路径数量

思路 ：dp