UVa 10487 - Closest Sums

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

從集合中找出兩個不相同的數相加後與 k 最接近。

Solution

窮舉出每一個 k - num[i] 也就是 i = 0 ~ n-1 ，在從集合裡利用二分找出 x 使 k - num[i] + num[x] 最接近 k 的 (這裡直接使用 std::lower_bound )，再比較這些看誰最接近 k 。

在二分搜後如果沒有找到剛好可以等於 k 的，不確定大於 k 還是小於 k 會更接近 k ，所以多判斷了一下，如果總和大於 k ( std::lower_bound 會找第一個大於等於的)，就去比較小於的:

if (num[idx] > diff && (idx - 1) != i)
    {
        temp = ABS(diff - num[idx - 1]);
        if (temp < diff2)
        {
            idx--;
            diff2 = temp;
        }
    }

(下面完整 code 可能比較容易理解)

Code

UVa 10487UVa 10487 - Closest Sums

#include<cstdio>
#include<algorithm>
#include<climits>
#define ABS(a) ((a)<0?(-(a)):(a))

int num[1000];
int binary_search(int n, int tar);
int main()
{
    int i;
    int n, Case = 0;
    while (scanf("%d", &n) && n)
    {
        printf("Case %d:\n", ++Case);

        for (i = 0; i < n; i++)
            scanf("%d", &num[i]);
        std::sort(num, num + n);

        int m, temp;
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &temp);
            printf("Closest sum to %d is %d.\n", temp, binary_search(n, temp));
        }
    }

    return 0;
}
int binary_search(int n, int tar)
{
    int min = INT_MAX, ans;
    for (int i = 0; i < n - 1; i++)
    {
        int diff = tar - num[i], diff2, temp;
        int idx = std::lower_bound(num + i + 1, num + n, diff) - num;
        if (idx == n)//沒找到大於等於的
            idx = n - 1;

        diff2 = ABS(diff - num[idx]);//兩者之和與 tar 的差

        //判斷 num[idx] 和 num[idx-1] 哪個可使與 tar 的差距更小
        if (num[idx] > diff && (idx - 1) != i)
        {
            temp = ABS(diff - num[idx - 1]);
            if (temp < diff2)
            {
                idx--;
                diff2 = temp;
            }
        }
        
        //找出離 tar 最近的
        if (min > diff2)
        {
            min = diff2;
            ans = num[idx] + num[i];
        }
    }

    return ans;
}