时间戳

首页 > 技术文章 > hdu 2566 统计硬币

hdu 2566 统计硬币

crazyapple 2013-09-10 21:09 原文

http://acm.hdu.edu.cn/showproblem.php?pid=2566

假设一堆由1分、2分、5分组成的n个硬币总面值为m分，求一共有多少种可能的组合方式（某种面值的硬币可以数量可以为0）。
输入数据第一行有一个正整数T，表示有T组测试数据；
接下来的T行，每行有两个数n,m，n和m的含义同上。
对于每组测试数据，请输出可能的组合方式数；
每组输出占一行。
Sample Input
2
3 5
4 8
Sample Output
1
2
 
【题解】： 这里没有给出n，m的范围，建议使用第三种【code3】方式解
 
【code1】：暴力O(N*N)
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     while(t--)
12     {
13         int i,n,m,j;
14         scanf("%d%d",&n,&m);
15         int cnt=0;
16         for(i=0;i<=m/5;i++)
17         {
18             for(j=0;j<=m/2;j++)
19             {
20                 if(n-i-j+j*2+i*5==m&&n-i-j>=0)
21                 {
22                     cnt++;
23                 }
24             }
25         }
26         printf("%d\n",cnt);
27     }
28     return 0;
29 }

 

【code2】：暴力 O（N）
　　似乎只要1、2、5，硬币的个数中的一个固定了，另外两个也就一定

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     while(t--)
12     {
13         int i,n,m;
14         scanf("%d%d",&n,&m);
15         int cnt=0;
16         for(i=0;i<=m/5;i++)
17         {
18             int ln = n-i;
19             int lm = m-i*5;
20             if(lm>=ln&&lm<=2*ln)
21             {
22                 cnt++;
23             }
24         }
25         printf("%d\n",cnt);
26     }
27     return 0;
28 }

 

 【code3】：优化（推荐）
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int t;
10     scanf("%d",&t);
11     while(t--)
12     {
13         int n,m,mins,maks;
14         scanf("%d%d",&n,&m);
15         if(m>=n)    maks=(m-n)/4;
16         else
17         {
18             puts("0");
19             continue;
20         }
21         if(m-2*n>=0)
22         {
23             if((m-2*n)%3 == 0)
24                 mins=(m-2*n)/3;
25             else
26                 mins=(m-2*n)/3 + 1;
27         }
28         else mins=0;
29         printf("%d\n",maks-mins+1);
30     }
31     return 0;
32 }

 

推荐阅读