PAT A1068 Find More Coins (30分) 用的递归 有没有大佬能帮我看看这道题哪里错了

Question

问题描述：
有N枚硬币，给出每枚硬币的价值，现在要用这些硬币去支付价值为M的东西。
问是否可以找见这样的方案，使得选择用来支付的硬币价值之和恰好为M，如果不存在，输出NoSolution。
如果存在，从小到大输出选择用来支付硬币的价值，如果有多种方案，则输出字典序最小的那个。（A1 = B1, A2 = B2 , ...... Ai = Bi 但 A(i+1) < B(i+1)

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 10010;
int a[maxn];
int n, m;
multiset<int> s;
void find_sequence(int left, int right, int val)
{

    while(left < right && a[left]+a[right]!=val)
    {
        if(a[left]+a[right] < val && left < right)
        left++;
        else if(a[left]+a[right] > val && right > left)
        right--;
    }
    if(a[left]+a[right] == val)
    {
        s.erase(val);
        s.insert(a[left]);
        s.insert(a[right]);
        find_sequence(left+1, right-1, a[right]);
    }
    if(left >= right)
    return;

}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    find_sequence(0,n-1,m);

    if(s.size() < 2)
    {
        printf("No Solution\n");
        return 0;
    }

    auto x = --s.end();
    for(auto i = s.begin(); i != s.end();i++)
    {
        printf("%d", *i);
        if(i != x)
        printf(" ");
    }
    return 0;
}

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

首先，这个问题可以通过双指针解决。我们可以先对硬币价值进行排序，然后设置两个指针left和right，分别指向价值最小的硬币和价值最大的硬币。然后，我们通过移动指针left和right来寻找两个硬币的和等于所需支付的价值M。 如果找到两个硬币使得它们的和等于M，我们将这两个硬币的价值加入到一个容器中（这里使用multiset），然后继续在剩余的硬币中寻找，直到不再存在满足条件的硬币对。 如果最终容器中存放的硬币不足两个，则输出"No Solution"；如果存在满足条件的硬币对，则按照字典序从小到大输出选择的硬币价值。 以下是完整的代码实现：

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int a[maxn];
int n, m;
multiset<int> s;
void find_sequence(int left, int right, int val) {
    while (left < right && a[left]+a[right] != val) {
        if (a[left]+a[right] < val && left < right)
            left++;
        else if (a[left]+a[right] > val && right > left)
            right--;
    }
    if (a[left]+a[right] == val) {
        s.erase(val);
        s.insert(a[left]);
        s.insert(a[right]);
        find_sequence(left+1, right-1, a[right]);
    }
    if (left >= right)
        return;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a+n);
    find_sequence(0, n-1, m);
    if (s.size() < 2) {
        printf("No Solution\n");
        return 0;
    }
    auto x = --s.end();
    for (auto i = s.begin(); i != s.end(); i++) {
        printf("%d", *i);
        if (i != x)
            printf(" ");
    }
    return 0;
}

例如，对于输入：

5 8
1 2 3 4 5

输出：

3 5