hdu 2566 统计硬币

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

假设一堆由1分、2分、5分组成的n个硬币总面值为m分，求一共有多少种可能的组合方式（某种面值的硬币可以数量可以为0）。

输入数据第一行有一个正整数T，表示有T组测试数据；
接下来的T行，每行有两个数n,m，n和m的含义同上。

对于每组测试数据，请输出可能的组合方式数；
每组输出占一行。

Sample Input

3 5

4 8

Sample Output

【题解】：这里没有给出n，m的范围，建议使用第三种【code3】方式解

【code1】：暴力O(N*N)

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int i,n,m,j;

         scanf("%d%d",&n,&m);

         int cnt=;

         for(i=;i<=m/;i++)

         {

             for(j=;j<=m/;j++)

             {

                 if(n-i-j+j*+i*==m&&n-i-j>=)

                 {

                     cnt++;

                 }

             }

         }

         printf("%d\n",cnt);

     }

     return ;

 }

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

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int i,n,m;

         scanf("%d%d",&n,&m);

         int cnt=;

         for(i=;i<=m/;i++)

         {

             int ln = n-i;

             int lm = m-i*;

             if(lm>=ln&&lm<=*ln)

             {

                 cnt++;

             }

         }

         printf("%d\n",cnt);

     }

     return ;

 }

【code3】：优化（推荐）

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int n,m,mins,maks;

         scanf("%d%d",&n,&m);

         if(m>=n)    maks=(m-n)/;

         else

         {

             puts("");

             continue;

         }

         if(m-*n>=)

         {

             if((m-*n)% == )

                 mins=(m-*n)/;

             else

                 mins=(m-*n)/ + ;

         }

         else mins=;

         printf("%d\n",maks-mins+);

     }

     return ;

 }

巴特西

hdu 2566 统计硬币

最新文章

热门文章