题目描述:给定包含N个数的无序数组S(可能包含负数,0,正数)。求三个数A,B,C,使其和的绝对值最小。
例如:S={-9,0,1,3,6},A=-9,B=3,C=6,MIN=0
算法解析:
解法一:枚举3个数,O(N*N*N)
解法二:对S排序后枚举其中2个数,二分查找另一个数。O(N*N*LOGN)
解法三:对S排序后枚举其中1个数X,使用双向指针i,j从数组两端更新(注意剔除X)。根据S[I]+S[J]+X的正负号来更新I或J。若为负则I++,否则J--。一旦和为0即退出。同时根据此和来更新best。最后best即为所求。利用三个变量X,Y,Z可得到任一最优解。
例如S={-9,0,1,3,6}
X=-9
0 1 3 6 10
i j
X+S[i]+S[j]=-9+0+10=1 > 0 j--
0 1 3 6 10
i j
X+S[i]+S[j]=-9+0+6=-3 < 0 i++
0 1 3 6 10
i j
X+S[i]+S[j]=-9+1+6=-2 < 0 i++
0 1 3 6 10
i j
X+S[i]+S[j]=-9+3+6=0 = 0 quit
MIN=0,X=-9,Y=3,Z=6;
Code:
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <algorithm> using std::sort;
int main() { int a[100], b[100]; int X,Y,Z; int i, j, k; int best; srand((unsigned)time(NULL)); int KASE = rand()%10; for(int kase = 1; kase <= KASE; kase++){ printf("\nCase #%d :\n", kase); int n = rand()%20; if(n <= 2) { printf("Sorry, n is less than 3. \n"); continue; } for(i = 0; i < n; i++){ a[i] = rand()%100; if(rand()%2) a[i] *= -1; } sort(a,a+n); for(i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); int STD = 1000000; for(i = 0; i < n; i++) for(j = i+1; j < n; j++) for(k = j+1; k < n; k++) if(abs(a[i]+a[j]+a[k]) < STD){ X = a[i]; Y = a[j]; Z = a[k]; STD = abs(a[i]+a[j]+a[k]); } printf("STD answer is: MIN=%d, X=%d Y=%d Z=%d\n", STD, X, Y, Z); best = 1000000; for(i = 0; i < n; i++){ int cur = a[i]; int cnt = 0; for(j = 0; j < n; j++){ if(j != i) b[cnt++] = a[j]; } int head = 0, tail = n-2; while(head < tail){ int now = cur + b[head] + b[tail]; if(now == 0 || abs(now) < best){ best = abs(now); X = cur; Y = b[head]; Z = b[tail]; if(now == 0) break; } if(now < 0) head++; else tail--; } if(best == 0) break; } printf("My answer is: MIN=%d, X=%d Y=%d Z=%d\n", best, X, Y, Z); } system("pause"); }
|
阅读(1368) | 评论(0) | 转发(0) |