UVa 11057 - Exact Sum

Contents

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

Problem

題目網址

找兩個數字相加起來剛好等於 money ，且兩數字相差最小。

Solution

都先排序。
接著提供兩個做法，一個是直接找大於等於 money/2 的當其中一個數，看有沒有辦法用小於它的來相加成 money。先找到的兩者相差一定較小，即為答案。

另一種比較慢，直接窮舉每個 price[i] 找 money-price[i] ，再比較差值取最小的。

Code

(1)

UVa 11057

#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
    int n, price[10001];

    while (scanf("%d", &n) != EOF)
    {
        int money;
        for (int i = 0; i < n; i++)
            scanf("%d", &price[i]);
        scanf("%d", &money);

        sort(price, price + n);
        int mid = lower_bound(price, price + n, money / 2) - price;//第一個大於等於 money/2 的
        bool flag = true;

        //從中間向兩側去找，先找到的他們相差一定比較小
        for (; flag&&price[mid] <= money; mid++)//向右
            for (int i = 1; i <= mid; i++)//向左
                if (price[mid] + price[mid - i] == money)
                {
                    printf("Peter should buy books whose prices are %d and %d.\n\n", price[mid - i], price[mid]);
                    flag = false;
                    break;
                }
    }

    return 0;
}

(2)

UVa 11057

#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
    int n, price[10001];

    while (scanf("%d", &n) !=EOF)
    {
        int diff = 1e9, a, b, money;
        for (int i = 0; i < n; i++)
            scanf("%d", &price[i]);
        scanf("%d", &money);

        sort(price, price + n);
        for (int i = 0; i < n - 1 && money >= price[i]; i++)
        {
            int* p = find(price + i, price + n, money - price[i]);//看有沒有另一個數可以讓它們相加等於 money
            if (p == price + n)
                continue;
            else
            {
                if (*p - price[i] < diff)
                {
                    a = price[i];
                    b = *p;
                    diff = b - a;
                }
            }
        }

        printf("Peter should buy books whose prices are %d and %d.\n\n", a, b);
    }

    return 0;
}