match 匹配

第一眼的感觉是二分图匹配，但复杂度较高，最佳得分为50。其实仔细观察可以发现，将a从小到大枚举，b的可选区间是单调向右移动的。我们每次贪心，都取区间最左边未取的点，既可以得到最大对数。

这里有dp，但其实也没必要。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+1000;
int n,m,x,y;
int a[maxn],b[maxn];
int f[maxn],g[maxn];
int l,r;
int main(){
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&b[i]);
    l=0,r=0;
    while(b[l]<a[1]-x) l++;
    while(b[r+1]<=a[1]+y) r++;
    if(l<=r) f[1]=l,g[1]=1;
    else f[1]=0,g[1]=0;
    for(int i=2;i<=n;i++){
        while(b[l]<a[i]-x) l++;
        while(b[r+1]<=a[i]+y) r++;
        if(l>r||f[i-1]>=r) f[i]=f[i-1],g[i]=g[i-1];
        else f[i]=max(l,f[i-1]+1),g[i]=g[i-1]+1;
    }
    cout<<g[n]<<endl;
    return 0;
}