题目概述
给你 \(n\) 个数 \(a_i\)。
求：\(\max_{i\ne j\ne k}(a_i+a_j)\bmod a_k\)。
分析
好题！
我一开始看到是无从下手的。
但是细想一下，关键点在于 \(a_k\)，所以的说，枚举 \(a_k\) 是必不可少的。
然后我们令剩余的数全部对 \(a_k\) 取模，得到答案的途径有两种：
- \(b_i+b_j\geq a_k\)，因为两者相加最多减去一个 \(a_k\)，这种情况直接取两个最大的就行了，时间复杂度 \(mathcal{O}(n\log n)\)。
- \(b_i+b_j< a_k\)，这个用 \(l,r\) 双指针框住区间取两端即可，相当于枚举 \(l\)，那么所对应的 \(r\) 是单调递减的，时间复杂度 \(\mathcal{O}(n\log n)\)。
两者都需要先排序。
对于每一个 \(a_k\) 都做一遍这个我们是承担不起的。
那么贪心地先做大的 \(a_k\)，这个是显然的。
如果过说我现在的 \(ans\) 不小于当前的模数（因为在此种情况下不可能存在更大的解），直接退出即可。
那么这个剪枝是很强的（还需要注意对于相等的 \(a_k\) 只做一遍，怕那种全都是一样的数据）。
可以证明一下。
代码
时间复杂度 \(\mathcal{O}(n\log V\log n)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
#define N 200005
using namespace std;
int n,a[N],b[N];
int solve(int id) {int cnt = 0;for (int i = 1;i <= n;i ++)if (i != id) b[++cnt] = a[i] % a[id];stable_sort(b + 1,b + 1 + cnt);int res = (b[cnt] + b[cnt - 1]) % a[id];for (int l = 1,r = cnt;l < r;l ++) {while(l < r && b[r] + b[l] >= a[id]) r --;if (l < r) res = max(res,b[l] + b[r]);}return res;
}
signed main(){cin >> n;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]);stable_sort(a + 1,a + 1 + n,greater<int>());int ans = 0;for (int i = 1;i <= n;i ++) {if (ans >= a[i]) break;if (a[i] == a[i - 1]) continue;ans = max(ans,solve(i));}cout << ans;return 0;
}
证明时间复杂度
假设：
\[a_1>a_2>\dots>a_x>ans>a_{x+1}>\dots>a_n
\]
因为 \(ans\) 是最大的答案，根据第一部分我们对于任意 \(i(1\leq i\leq x-2)\) 有：
\[(a_{i+1}+a_{i+2})\bmod a_i\leq ans
\]
因为：
\[a_i>a_{i+1}>a_{i+2}>ans
\]
所以：
\[(a_{i+1}+a_{i+2})\bmod a_i\leq ans<a_{i+1}+a_{i+2}<2a_i
\]
因此我们至少有：
\[a_i\leq a_{i+1}+a_{i+2}<2a_i
\]
这就说明了中间的那个式子要是与左边的式子多加上一个 \(a_i\) 比较那肯定是变小的。
我们此时联系上一个式子，把 \(ans\) 换代进来也是一样地有：
\[ans<a_{i+1}+a_{i+2}<ans+a_i
\]
注意后面的式子，我们考虑同构，于是左右两边同时减去 \(2ans\) 有：
\[(a_{i+1}-ans)+(a_{i+2}-ans)<a_i-ans
\]
同构了！令 \(f_i=a_i-ans\) 那么有：
\[f_{i+1}+f_{i+2}<f_i
\]
这很像一个倒着的斐波那契数列，这个东西是呈指数级增长的，所以说是 \(\mathcal{O}(\log V)\) 的时间复杂度。
真神啊这题！