uva 10487 Closest Sums (遍歷&二分查找&&雙向查找)

題目大意：先給定n個數字，現在要求算出這n個數字的兩兩之和保存到sum數組，然後在給定m個數，要求找到和每一個數最接近的sum[i]；

挨個計算每個屬於其他數之間的sum，然後排序；

查找時有兩種方法：二分查找&&雙向查找；當然二分查找的效率比後者高了很多，但是都能AC。

提供一條新思路，並不一定非要用二分。

雙向查找：

#include
#include
#include
using namespace std;
int n,m;
int a[1000010];
int a1[1010];
int ans;
int main()
{
    int cnt=0;
    while(scanf("%d",&n)!=EOF&&n)
    {
        cnt++;
        printf("Case %d:\n",cnt);
        for(int i=0; i=t/2; i++,j--)//雙向查找；
            {
                if(a[i]>=b)
                {
                    bb=i;
                    break;
                }
                if(a[j]<=b)
                {
                    bb=j;
                    break;
                }
            }
            if(a[bb]==b)
                ans=a[bb];
            else
            {
                if(a[bb]b-a[bb])
                        ans=a[bb];
                    else
                        ans=a[bb+1];
                }
                else if(a[bb]>b&&bb!=0)
                {
                    if(b-a[bb-1]>a[bb]-b)
                        ans=a[bb];
                    else
                        ans=a[bb-1];
                }
                else
                    ans=a[bb];
            }
            printf("Closest sum to %d is %d.\n",b,ans);
        }
    }
    return 0;
}

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
#define MAXN 1010  
  
int n , m , len;  
int num_n[MAXN] ,num_m[MAXN];  
int sum[1000010];  
//二分查找  
void Binary_Search(int a){  
    int left , right , mid , ans;  
    left = 0 ; right = len-1;  
    while(1){  
        if(right-left == 1){  
            ans = (sum[right]-a)<(a-sum[left])?sum[right]:sum[left];  
            break;  
        }  
        mid = (left+right)/2;  
        if(sum[mid] > a)  right = mid;  
        if(sum[mid] < a)  left = mid;  
        if(sum[mid] == a) {ans = a ; break;}  
    }  
    printf("Closest sum to %d is %d.\n" , a , ans);  
}  
  
void solve() {  
    int i , j , k;  
    for(i = 0 , k = 0 ; i < n ; i++){  
        for(j = i+1 ; j < n ; j++)  
            sum[k++] = num_n[i]+num_n[j];  
    }  
    len = k ; sort(sum , sum+k);  
    for(i = 0 ; i < m ; i++)  
        Binary_Search(num_m[i]);   
}  
  
int main() {  
    //freopen("input.txt" , "r" , stdin);  
    int cnt = 1;  
    while(scanf("%d%*c" , &n) && n){     
        for(int i = 0 ; i < n ; i++)  
            scanf("%d%*c" , &num_n[i]);  
        scanf("%d%*c" , &m);  
        for(int i = 0 ; i < m ; i++)  
            scanf("%d%*c" , &num_m[i]);  
        printf("Case %d:\n" , cnt++);  
        solve();  
    }  
    return 0;  
} 

下面這個快：

#include  
#include  
#include  
using namespace std;  
#define sf scanf  
#define pf printf  
const int INF=0x3f3f3f3f;  
  
int a[1005];  
int cas = 0, n, m, query, closest, diff, i, j;  
  
inline void find()  
{  
    if (j == n || j != i + 1 && diff - a[j - 1] < a[j] - diff)  
    {  
        if (diff - a[j - 1] < abs(closest - query))  
            closest = a[i] + a[j - 1];  
    }  
    else  
    {  
        if (a[j] - diff < abs(closest - query))  
            closest = a[i] + a[j];  
    }  
}  
  
int main()  
{  
    while (sf("%d", &n), n)  
    {  
        for (i = 0; i < n; ++i)  
            sf("%d", &a[i]);  
        sort(a, a + n);  
        sf("%d", &m);  
        pf("Case %d:\n", ++cas);  
        while (m--)  
        {  
            sf("%d", &query);  
            closest = INF;  
            for (i = 0; i < n - 1; ++i)  
            {  
                diff = query - a[i];  
                j = lower_bound(a + i + 1, a + n, diff) - a;  
                find();  
            }  
            pf("Closest sum to %d is %d.\n", query, closest);  
        }  
    }  
    return 0;  
}