Codeforces Round #183 (Div. 1) C. Minimum Modular

题目链接：http://codeforces.com/contest/303/problem/C题意：给n个数a[i], 在最多去除 k 个数的情况下，找出最小的 m ，使得 ，即n个数中任意两个数 膜m 不相等算法：暴力+剪枝思路： 可转化为 a[i]-a[j] != *m，其中k为任意正整数。 - 记录下所有a[i]-a[j] 差值的出现次数，将 a[i]-a[j]==k*m 的出现次数累加，若其大于 k*(k+1)/2 则说明即使将该造成该差值的数除去k个，仍然会造成该差值，所以将其剪枝。 - 如此一来，n个数中出现的膜m后重复的数，最多为4个（k<=4）。 - 如此剪枝后，再精细得比对是否有膜m后的重值

---

#include <bits/stdc++.h> #define pi acos(-1) using namespace std; typedef long long LL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const LL ll_INF = 0x3f3f3f3f3f3f3f3f; const int N = 5000 + 10; const LL mod = 1e9 + 7; int a[N], d[1000010], mark[N]; int main() { //memset(mark, 0, sizeof(mark)); int n, k; scanf("%d%d", &n, &k); for(int i=0; i<n; i++) scanf("%d", &a[i]); sort(a, a+n); for(int i=0; i<n; i++) for(int j=0; j<i; j++) d[a[i]-a[j]]++; for(int p=1; ; p++){ int tot=0; for(int i=p; i<=a[n-1]; i+=p) if((tot+=d[i]) > k*(k+1)/2) break; if(tot > k*(k+1)/2) continue; int sum=0; for(int i=0; i<n && sum<=k; i++){ sum += (mark[a[i]%p]==p); mark[a[i]%p]=p;// =p 用来更新，不然，如果=1 的话，需要每个循环初始化一次 } if(sum<=k){ printf("%d\n", p); return 0; } } }