CVBB ACM Team

存在 $f[i]+g[i]>n$ 则无解（鸽巢原理）。

解法一：反序，设重叠部分值为 $i$，用两端均不等于 $i$ 的部分替换，可证 $n-a-b + a\capb=n-f[i]-g[i]+a\capb>= a\capb$，故满足所有 $i$ 使得 $f[i]+g[i]<n$ 则有解。

解法二：按 $f[i]+g[i]$ 大小顺序匹配，选择一个 $i={\max\arg}_{i} f[i]+g[i]$，将之与任意 $j$ 匹配，问题规模化为 $n-1$，当存在 $j$ 使得 $f[i]+g[i]==f[j]+g[j]$ 均为最大值时，只剩两种元素，互相匹配即可。