• 博客访问： 156968
• 博文数量： 37
• 博客积分： 2510
• 博客等级： 少校
• 技术积分： 307
• 用 户 组： 普通用户
• 注册时间： 2008-04-01 11:02

2011年（1）

2009年（1）

2008年（35）

2009-10-07 23:20:12

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 #include #include #include 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");}`