跃2.0 2017-01-07 07:20 采纳率: 40%
浏览 3002
已采纳

acm 里硬币问题 具体题目见下,采用穷举法时间超限,请问怎么修改

主页 讨论版 问题 名次 状态 统计
问题 L: 还是硬币问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 183 解决: 30
状态
题目描述
给你无限多个1元的硬币和2元的硬币,还有5元的硬币。

现在要你从这3种硬币中取n个硬币,使得他们的价值和为m

输入
多组输入

每组n , m

n < 1e6 , m <1e6

输出
总的方案数目

样例输入
2 3
样例输出
1

#include
int main()
{
int n,m;
int x,y,z,i,k,j;
i=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(x=0; x<=n; x++)
{
for(y=0; y<=n-x; y++)
{
for(z=0; z<=n-x-y; z++)
{
if((x+y+z==n)&&(x+2*y+5*z==m))
{
i++;
}

            }
        }
    }
    printf("%d\n",i);
}
return 0;

}

  • 写回答

5条回答

  • 呆的久 2017-01-08 02:48
    关注

    假设1元,2元,5元硬币分别为a,b,c个

    求满足约束条件
    a + b + c = n            (1)         
    的情况下,
    a + 2*b + 5*c = m    (2)
    解的个数。
    

    直接用(1) - (2), 得到公式(3)

     b + 4c = m-n        (3)
     a被消去了,因为
     0 <= a <= n
     所以约束条件变为,
     0 <= b + c <= n
    

    最终就变成了求
    b+4c = m - n
    有多少组整数解的问题

    int resolve(int n, int m) {
        int b = 0, c = 0;
        int temp = m - n;
        int sum = 0;
    
        if ((temp % 4) > n) return 0;
    
        for (int c = (temp/4); c >= 0; --c) {
            b = temp - (c * 4);
            if (b + c <= n)
                sum += 1;
            else
                break;
        }
    
        return sum;
    
    }
    
    

    思路大概这样,代码随手写得...

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(4条)

报告相同问题?

悬赏问题

  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)