Reading

AGC032E Modulo Pairing

Fanyi Pu

给一个长度为 2n 的序列，要求将其两两匹配成 n 组，假设第 i 组为 (xi,yi)，求 maxi=1n(xi+yi)modm 的最小值，1≤n≤105,1≤m≤109,0≤ai<m。

我们首先我们有：

(x+y)modm={x+yx+y≤mx+y−mx+y>m

接下来我们看几种情况：

按是否取模区分的四种区间配对调整情况

如果我们有 x1≤x2≤x3≤x4，那么我们有这样 4 中情况：

第一种，x3+x4<m，那显然 (x1,x4),(x2,x3) 更优。

第二种，x1+x2≥m，和第一种一样。

第三种，{x1+x3<mx2+x4≥m，考虑到 x2+x4−m<x2，故有 max{x1+x3,x2+x4−m}=x1+x3，而考虑到 {x1+x2≤x1+x3x3+x4−m<x3，故有 max{x1+x3,x2+x4−m}≥max{x1+x2,x3+x4−m}。所以 (x1,x2),(x3,x4) 一定比 (x1,x3),(x2,x4) 优。

我们再来看 (x1,x4),(x2,x3) 的情况。如果有 {x1+x4≥mx2+x3≥m，那就有 {x1+x4−m<x1x2+x3−m<x2，所以 max{x1+x4−m,x2+x3−m}<x2≤max{x1+x2,x3+x4−m}，此时 (x1,x4),(x2,x3) 的方案更优。但是如果有 x1+x4≤m 或是 x2+x3≤m，则答案将会更大。

第四种，{x1+x4<mx2+x3<mx3+x6≥mx4+x5≥m。根据前面的讨论，我们仅需比较 (x1,x4),(x2,x3),(x5,x6) 和 (x1,x2),(x3,x4),(x5,x6) 即可，不难发现 {x1+x2≤x1+x4x3+x6−m<x3≤x2+x3x4+x5−m≤x5+x6−m，于是 max{x1+x2,x3+x6−m,x4+x5−m}≤max{x1+x4,x2+x3,x5+x6−m}。

根据第一、二、三种情况，我们发现，最终的划分结果肯定是被分成两部分，左边部分最小的匹配，次大的和次小的匹配……右边也这样匹配。其中左边所有的匹配 (x,y) 都有 x+y<m，右边的匹配 (x,y) 都有 x+y≥m。

根据第四种情况，我们可以发现蓝色的匹配数越多越好，于是我们考虑二分蓝色的匹配数量，最终确定答案。

代码可以看这里。

cpp
#define _CRT_SECURE_NO_WARNINGS

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

namespace pufanyi {

    inline char gc() {
        static const int L = 233333;
        static char sxd[L], *sss = sxd, *ttt = sxd;
        if (sss == ttt) {
            ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
            if (sss == ttt) {
                return EOF;
            }
        }
        return *sss++;
    }

#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
    inline char readalpha() {
        char dd;
        for (; !isalpha(c); dd);
        return c;
    }

    inline char readchar() {
        char dd;
        for (; c == ' '; dd);
        return c;
    }

    template <class T>
    inline bool read(T& x) {
        bool flg = false;
        char dd;
        x = 0;
        for (; !isdigit(c); dd) {
            if (c == '-') {
                flg = true;
            } else if(c == EOF) {
                return false;
            }
        }
        for (; isdigit(c); dd) {
            x = (x << 1) + (x << 3) + (c ^ 48);
        }
        if (flg) {
            x = -x;
        }
        return true;
    }
#undef dd

    template <class T>
    inline void write(T x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x < 10) {
            putchar(x | 48);
            return;
        }
        write(x / 10);
        putchar((x % 10) | 48);
    }

    template <class T>
    inline void writesp(T x) {
        write(x);
        putchar(' ');
    }

    template <class T>
    inline void writeln(T x) {
        write(x);
        puts("");
    }

    typedef long long LL;

    const int maxn = 200005;

    int n, m;
    int aa[maxn];

    inline bool check(int x) {
        int lim = x << 1;
        for (int l = lim + 1, r = n << 1; l < r; ++l, --r) {
            if (aa[l] + aa[r] < m) {
                return false;
            }
        }
        return true;
    }

    int Main() {
        read(n), read(m);
        for (int i = 1; i <= n << 1; ++i) {
            read(aa[i]);
        }
        sort(aa + 1, aa + (n << 1) + 1);
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int ans = 0;
        int lim = l << 1;
        for (int l = 1, r = lim; l < r; ++l, --r) {
            ans = max(ans, (aa[l] + aa[r]) % m);
        }
        for (int l = lim + 1, r = n << 1; l < r; ++l, --r) {
            ans = max(ans, (aa[l] + aa[r]) % m);
        }
        writeln(ans);
        return 0;
    }

}

int main() {
    return pufanyi::Main();
}

Cite this post

@misc{pu2020oiicpcatcoderagc032e,
  author = {Pu, Fanyi},
  title  = {AGC032E Modulo Pairing},
  year   = {2020},
  month  = {2},
  url    = {https://pufanyi.com/blog/oi-icpc/atcoder/agc032-e}
}