题解：AT_agc032_e [AGC032E] Modulo Pairing

· · 题解

NOIP 模拟赛 T1 ，场切 *3400 祭

做法不算排序复杂度 O(n)，但是懒得写基排。

首先我们发现一对权值 (x,y) 合并后新的权值有两种情况： x+y 或者 x+y-M，如果是后面一种需要满足 x+y>M。

然后我们考虑，假如我们已经知道了答案，那么所有比答案大的权值 x 必然被合并到某对 (x,y) 使得新的权值为 x+y-M，那么排序后这些 x 在 a 序列中是一个后缀。

于是我们考虑把 a_i-M 也加入 a 序列然后排序，这样有什么用处呢？

我们发现这个新的序列任何一个长度为 n 的连续子序列都包含了原序列的所有数，其中为负数的值表示你这个值需要匹配之后新的权值 >M。

于是我们在新序列上枚举左端点，那么对于这个新的子序列，它的最优答案显然是从两端向中间匹配（因为你不用像官方题解那样考虑取模之后变小的情况），当然，如果你匹配的时候出现了负数值，那么,相当于说明你这一对匹配的权值和 <M，这个匹配显然是不行的。

于是你 O(n^2) 做完了，然后考虑优化，发现这个子序列左端点越左越好，问题就是如何找到最左的左端点。

我赛时想到一个感觉很神仙的做法：

考虑从中间往两边扩展，初始 l=mid,r=mid+1，每次扩展就是 l--,r++。对于当前的一对 (l,r)，如果 a_l+a_r<0，那么 l++,r++，这样显然是可行的。

证明：考虑归纳证明，初始情况时，a_l 是负数，a_r 和 a_{r+1} 都不是负数，那么显然可行。

当 (l,r) 满足条件时，考虑 (l-1,r+1)，由于 a_l+a_r\ge0，那么 a_l+a_{r+2}\ge 0，内部的其他点也同理，所以 (l,r+2) 一定是一个合法匹配，所以得证！

然后直接做就行了，复杂度 O(n\log n)。

代码贼短。

#include<bits/stdc++.h>
#define usefile(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout);
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fu(i,a,b) for(int i=(a);i<(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define ll long long
using namespace std;
const int N=2e5+5;
int n,m,a[N<<1],k;
int main()
{
    scanf("%d%d",&n,&m);int nn=n<<1;k=nn<<1;
    fo(i,1,nn)scanf("%d",&a[i]),a[i+nn]=a[i]-m;
    sort(a+1,a+k+1);
    int anss=0;
    int l=nn+1,r=nn;
    while(r-l+1<nn)
    {
        --l;++r;
        if(a[l]+a[r]<0)++l,++r;
    }
    while(l<=r)anss=max(anss,a[l]+a[r]),++l,--r;
    printf("%d",anss);
    return 0;
}