malloc_88 2020-04-24 17:24 采纳率: 0%
浏览 162

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

图片说明图片说明图片说明

问题描述:
有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;
}
  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 如何用stata画出文献中常见的安慰剂检验图
    • ¥15 c语言链表结构体数据插入
    • ¥40 使用MATLAB解答线性代数问题
    • ¥15 COCOS的问题COCOS的问题
    • ¥15 FPGA-SRIO初始化失败
    • ¥15 MapReduce实现倒排索引失败
    • ¥15 ZABBIX6.0L连接数据库报错,如何解决?(操作系统-centos)
    • ¥15 找一位技术过硬的游戏pj程序员
    • ¥15 matlab生成电测深三层曲线模型代码
    • ¥50 随机森林与房贷信用风险模型