方法一:可以暴力枚举,其实用枚举方法水过纯属意外。(可以试一下1000个1这组数据,它是跑不出来的。)
方法二:可以将问题转化为 a+b=d-c。这样,只要将a+b的值全部算出来,存至哈希表内,再枚举d,c的值看两边是否相等从而推出d,就可以将复杂度由O(n4)降之O(n2)左右的水准,便可以过了。
代码如下:
方法一(枚举 1.600s):
#define test #include <iostream> #include <algorithm> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; int a[1001], n; int solve() { int i, j, k, l; for(i = n - 1; i >= 0; i--) for(j = 0; j < n; j++) { if(i == j) continue; for(k = 0; k < n; k++) { if(k == j || k == i) continue; for(l = 0; l < n; l++) if(l != k && l != j && l != i) { if(a[i] == a[j] + a[k] + a[l]) { printf("%d\n", a[i]); return 1; } } } } return 0; } int main() { #ifdef test freopen("sample.txt", "r", stdin); #endif int num; while(scanf("%d", &n), n) { for(int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); num = solve(); if(!num) printf("no solution\n"); } return 0; }
方法二(哈希 0.140s):
#include <iostream> #include <algorithm> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; const int MAXSIZE = 500510; int a[1001]; int n, head[MAXSIZE], next[MAXSIZE]; struct SUM { int sum; int x, y; } b[MAXSIZE]; int Hash(int s) { int seed = (s >> 1) + (s << 1); return (seed & 0x7FFFFFFF) % 500503; } int insert(int s) { int h = Hash(b[s].sum); int u = head[h]; while(u) { if(b[u].sum == b[s].sum) return 0; u = next[u]; } next[s] = head[h]; head[h] = s; return 1; } int search(int x, int y) { int h = Hash(a[x] - a[y]); int u = head[h]; while(u) { if(a[x] - a[y] == b[u].sum && x != b[u].x && y != b[u].y && b[u].x != y && b[u].y != x ) // 判断a,b不能与c,d重复 return 1; u = next[u]; } return 0; } int main() { #ifdef test freopen("sample.txt", "r", stdin); #endif int num; int max_; while(scanf("%d", &n), n) { max_ = -0x7FFFFFFF; num = 1; memset(head, 0, sizeof(head)); for(int i=0; i<n; i++) scanf("%d", &a[i]); for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) { b[num].sum = a[i] + a[j]; if(insert(num)) { b[num].x = i; b[num].y = j; ++num; } } for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(i != j) { if(search(i, j) && max_ < a[i]) max_ = a[i]; } if(max_ == -0x7FFFFFFF) printf("no solution\n"); else printf("%d\n",max_); } return 0; }