题意：
给出n ( n < = 40）个数，问能否确定一个k使得在有限的次数里执行操作使得数组里至少有一半的数是相同的。每次操作指的是选出一些数让其减小k。求最大的k，如果k可以无限大输出− 1.
思路：
枚举数组内两两元素差值，对这些差值求两两之间的g c d，枚举g c d，看看有没有n / 2元素的差值是该g c d的倍数，如果是的话，说明k可以等于该g c d。求g c d的原因是如果两个数之间的差值为该g c d，那么一定可以通过若干次变换变为相等的数。
还有一种思路就是枚举两两之间差值的因子。
代码：
#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std; typedef long long ll; const int maxn = 55; int n, a[maxn]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int _; cin >> _; while (_--) { cin >> n; map<int, int>mp; for (int i = 1; i <= n; i++) cin >> a[i],mp[a[i]]++; bool flag = 0; for (int i = 1; i <= n; i++) { if (mp[a[i]] >= n / 2) { flag = 1; break; } } if (flag) { puts("-1"); continue; } set<int>sd; for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) sd.insert(abs(a[i] - a[j])); set<int>sg; for (auto t1 : sd) { for (auto t2 : sd) { sg.insert(gcd(t1, t2)); } } int ans = 0; for (auto it : sg) { if (!it) continue; for (int i = 1; i <= n; i++) { int tmp = 0; for (int j = 1; j <= n; j++) { int now = abs(a[i] - a[j]); if (now % it == 0) tmp++; } if (tmp >= n / 2) ans = max(ans, it); } } cout << ans << endl; } return 0; }
#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std; typedef long long ll; const int maxn = 55; int n, a[maxn]; int main() { int _; cin >> _; while (_--) { cin >> n; map<int, int>mp; for (int i = 1; i <= n; i++) cin >> a[i],mp[a[i]]++; sort(a + 1, a + 1 + n); bool flag = 0; for (int i = 1; i <= n; i++) { if (mp[a[i]] >= n / 2) { flag = 1; break; } } if (flag) { puts("-1"); continue; } set<int>sd; for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) sd.insert(abs(a[i] - a[j])); set<int>sy; for (auto it : sd) { for (int i = 1; i * i <= it; i++) if (it % i == 0) sy.insert(i),sy.insert(it/i); } int ans=1; /* for (auto it : sy) { cout << it << " " ; } puts("");*/ for (auto it : sy) {//枚举因子 for (int i = 1; i <= n/2+1; i++) { int tmp = 1; for (int j = i + 1; j <= n; j++) { int now = a[j] - a[i]; if (now % it == 0) tmp++; } //if (it == 13) cout << tmp << endl; if (tmp >= n / 2) ans = it; } } cout << ans << endl; } return 0; }
