感觉这题的思想可以借鉴
如果k为0，题目会简单许多
建立一个数组S,S[i]表示原数组中，有多少对两式相减等于i
那么如何判断i是否满足题意呢，只要看
S[i],S[2*i],S[3*i]....一直到n*i大于原数组中的最大值，如果这些都满足，就说明i是成立的，就是答案了
然而现在有k这个东西，所以我们只能用最原始的那种方法去判断
用一个标记数组vis,vis[p]表示A[j]%i等于p出现的次数。那么我们就可以统计到底有多少个取模后重复出现的次数，就能判断是否符合答案了
但是这个复杂度实在是太高了，，联想我们之前的想法，能不能有什么剪枝呢？
继续上面的方法处理数组S，将S[i],S[2*i],S[3*i]..... 的值都加起来，记为 cnt
会有0<=cnt<=n*(n-1)/2 其中当n全是i的倍数的时候，才会出现这种极端情况
又因为，如果想满足题意，又有n-k<=1，即n<=k+1
所以有cnt<=cnt<=n*(n-1)/2<=(k+1)*k/2
那么，如果我们发现了有cnt>(k+1)*k/2，那么不可能会成为答案，直接剪枝
如果可能成为答案，我们再用最原始的方法去记录A[j]%i每个值出现的次数看重复的是否大于k即可
其中，还在codeforces上看到vis里面有个小技巧~
如果vis只用0和1，那么理论来讲，我在第一层for循环里面的开头，每次都需要清空vis数组
但是这个代码并没有这样做，第一层for循环的循环变量是i
我们每次本来是给vis赋值1，我们却赋值的是i，然后判断的时候是判断vis[j]==i是否成立
这样的话，每次循环i+1后，以前的vis里的值都不可能等于现在的i,所以相当于是0了~
感觉这种写法好神奇
题目里还有个陷阱，当n-k<=1时，直接输出1。因为此时可以把n删成只有一个数字，所以取模1也满足条件了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;int A[MX], S[MX], vis[MX];
int main() {int n, k, Max = 0;scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++) {scanf("%d", &A[i]);Max = max(Max, A[i]);}for(int i = 1; i <= n; i++) {for(int j = i + 1; j <= n; j++) {S[abs(A[i] - A[j])]++;}}if(k >= n - 1) {printf("1\n");return 0;}int ans = 0;for(int i = n - k; i <= Max + 1; i++) {int cnt = 0, sign = false;for(int j = i; j <= Max + 1; j += i) {cnt += S[j];if(cnt > k * (k + 1) / 2) {sign = true;break;}}if(sign) continue;cnt = 0;sign = false;for(int j = 1; j <= n; j++) {if(vis[A[j] % i] != i) {vis[A[j] % i] = i;} else cnt++;if(cnt > k) {sign = true;break;}}if(sign) continue;ans = i;break;}printf("%d\n", ans);return 0;
}