条件a+b == d-c，O(n*n)枚举出所有的形如a+b的和，然后从大到小枚举d，在枚举c，二分找d-c。
主要是要用容斥排除c和d出现在和中，详细的过程见注释。
复杂度为O(n^2log(n^2))。
/********************************************************* * ------------------ * * author AbyssalFish * **********************************************************/ #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<queue> #include<vector> #include<stack> #include<vector> #include<map> #include<set> #include<algorithm> #include<cmath> #include<numeric> using namespace std; /* 容斥原理去重复 左边是枚举出来的,保证不等 可能出现重复的情况有： d 和 c同时出现 case 1 d+c == d-c -> c == 0 其中一个出现 前提 a or b != c or d case2 a+d == d-c, -> a == -c , 必要条件 a != c -> c != 0 如果不满足这个条件：找到的可能是d == d case3 d+b == d-c, -> b == -c case 2 3互斥 case4 a+c == d-c, -> a == d-2*c, 必要条件 a != d -> c != 0 case5 c+b == d-c -> b == d-2*c case 4 5互斥 case (2,3,4,5) 1互斥 */ const int maxn = 1e3, INF = 536870911+5; int n; int e[maxn+1], tab[maxn*maxn>>1]; bool vis[maxn]; int solve() { sort(e,e+n); int i, j, a, c, d, k; int sz = 0; for(i = 1; i < n; i++){ a = e[i]; for(j = 0; j < i; j++){ tab[sz++] = a+e[j]; } } sort(tab,tab+sz); e[n] = e[n]-1; for(j = 0; j < n; j++) { c = -e[j]; vis[j] = (*lower_bound(e,e+n,c) == c); // c == 0 || -c == a or b } tab[sz+1] = tab[sz] = tab[sz-1]-1; for(i = n; i--; ){ d = e[i]; for(j = 2; j < n; j++)if(i!=j){ c = e[j]; a = d-c; k = lower_bound(tab,tab+sz,a)-tab; if(c){ if(vis[j]) k++; if(*lower_bound(e,e+n,a-c) == a-c) k++; } else k++; if(a == tab[k]) return d; } } return INF; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif while(scanf("%d",&n),n){ for(int i = 0; i < n; i++) scanf("%d", e+i); int res = solve(); if(res < INF) printf("%d ", res); else puts("no solution"); } return 0; }
伪二分O(n^3) ???
int solve() { sort(e,e+n); int i, j, sum, lb, ub, tsum; for(i = n; i--; ){ for(j = 2; j < n; j++)if(i!=j){ sum = e[i]-e[j]; for(lb = 0,ub = j-1; lb < ub; ){ //状态是DAG tsum = e[lb]+e[ub]; if(tsum == sum) return e[i]; tsum > sum ? ub--:lb++; //O(n) } } } return INF; }