ACM模版

描述

题解

讨论区某大神的神奇解法，实在是精髓啊……具体的思路可以查看评论区该大神的详细代码注释。

这个题比较常规的解法是用二分，首先排序，然后二分查找每个倍数区间的最大值，比如说，对于 6 这个数，我们并不需要把大于 6 的每一个数都进行测试，只需要在 7∼12 、 13∼18 等区间分别找到最大值进行判断，如果存在的话。这个过程用二分可以完美解决，没毛病~~~

当然，我用的是某大神的神奇解法，向大神神一般的推导过程致敬，虽然并不知道是怎么推的……有些许贪心的意味，分别搞局部最大值，最后求全局最大值。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 2e5 + 10;

int n;
int a[MAXN];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main(int argc, const char * argv[])
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scan_d(a[i]);
    }

    sort(a, a + n);

    int res, tmp, j;
    j = res = tmp = 0;
    for (int i = 1; i < n; i++)
    {
        tmp = a[i] % a[i - 1];
        if (tmp > a[i] % a[j])
        {
            while (tmp > a[i] % a[j])
            {
                j++;
            }
        }

        while (a[i] % a[j + 1] > a[i] % a[j])
        {
            j++;
        }
        tmp = a[i] % a[j];

        res = max(res, tmp);
    }

    cout << res << endl;

    return 0;
}