UVA11057 【Exact Sum】

题目大意(:)给出(N)个整数和一个整数(M)，求(N)个数中差值最小且相加等于(M)的两个数。

看到差值最小，我们首先想到排序,二分，实际上这也就是本题的正解解法了。

首先我们对题目给出的(N)个整数进行排序，使整个序列变得单调，然后我们二分查找出第一个大于(M/2)的位置(pos)，然后设(l=pos-1,r=pos)，然后分别向左向右扩展(:)

• 若(d[l] + d[r] < M, r++;)
• 若(d[l] + d[r] > M, l--;)
• 若(d[l] + d[r] == M,)输出答案即可。

最后一点(:)此题继承了(UVA)的优良传统，读入和输出很毒瘤，最后输出的时候一定要记得加两个换行符(……)

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxn = 1e4 + 5;
int n, d[maxn], goal;

int main() {
    while (scanf("%d
", &n) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &d[i]);
        scanf("%d", &goal);
        std::sort(d + 1, d + n + 1);
        int pos = std::upper_bound(d + 1, d + n + 1, goal / 2) - d; // upper_bound找出第一个大于M/2的数
        // 具体upper_bound用法不懂得小伙伴可以自行百度
        if (pos >= 2 && d[pos - 1] + d[pos - 2] == goal)  //一个小小的优化
            printf("Peter should buy books whose prices are %d and %d.

", d[pos - 2], d[pos - 1]);
        else {
            int l = pos - 1, r = pos;
            while (l > 0 && r <= n) {
                if (d[l] + d[r] == goal) {
                    printf("Peter should buy books whose prices are %d and %d.

", d[l], d[r]);
                    // 毒瘤的输出
                    break;
                }
                else if (d[l] + d[r] > goal)
                    l--;
                else r++;
            }
        }
    }
    return 0;
}

完结撒花(✪ω✪)