[PAT-A] 1048 Find Coins

Java

测试点3、4超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] first = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(first[0]);
        int m = Integer.parseInt(first[1]);
        int[] val = new int[n];
        String[] sec = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            val[i] = Integer.parseInt(sec[i]);
        }

        Arrays.sort(val);
        int low = 0, high = n - 1;
        while (low < high) {
            if (val[low] + val[high] > m) {
                high--;
            } else if (val[low] + val[high] < m) {
                low++;
            } else if (val[low] + val[high] == m) {
                System.out.println(val[low] + " " + val[high]);
                return;
            }
        }
        System.out.println("No Solution");
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 10010, INF = 0x3f3f3f3f;

int n, m;
unordered_set<int> st;

int main() {
    cin >> n >> m;

    int v1 = INF, v2;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        int y = m - x;        // should x + y = m
        if (st.count(y)) {
            st.insert(x);
            if (x > y) swap(x, y);
            if (x < v1) v1 = x, v2 = y;
        } else st.insert(x);
    }

    if (v1 == INF) cout << "No Solution" << endl;
    else cout << v1 << " " << v2 << endl;

    return 0;
}