PAT A 1048 Find Coins (25 分)

一、思路

題目要求在所有錢币中找到v1、v2，使v1 + v2 == M，且v1盡可能小，也就是要求v2盡可能大。

是以将錢币按照面值排序，初始l = 0， r = N- 1，從兩側向中間收斂，若面值和小，則l++；面值和大則r–；

二、代碼

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    vector<int> val(N);
    for( int i = 0; i < N; ++i )
        scanf("%d", &val[i]);
    sort( val.begin(), val.end() );
    for( int l = 0, r = N - 1; l < r; )
    {
        if( val[l] + val[r] == M )
        {
            printf("%d %d", val[l], val[r]);
            return 0;
        }
        else if( val[l] + val[r] < M )
            ++l;
        else --r;
    }
    printf("No Solution");
}