站点图标 陌路寒暄

4.1.1 Beef McNuggets 麦香牛块

code

4.1.1 Beef McNuggets 麦香牛块

时间： 1ms        内存：64M

描述：

农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”，奶牛们说，“如果你用只有一次能装3块、6块或10块的三种包装盒装麦香牛块，你就不可能满足想要一次只想买1、2、4、5、7、8、11、14或17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”
你的任务是帮助这些奶牛。给出包装盒的种类数N(1<=N<=10)和N个代表不同种类包装盒容纳麦香牛块个数的正整数(1<=i<=256)，输出顾客不能用上述包装盒(每种盒子数量无限)买到麦香牛块的最大块数。如果在限定范围内所有购买方案都能得到满足，则输出0。 范围限制是所有不超过2,000,000,000的正整数。

输入：

第1行: 包装盒的种类数N
第2行到N+1行: 每个种类包装盒容纳麦香牛块的个数

输出：

输出文件只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或0(如果在限定范围内所有购买方案都能得到满足)。

示例输入：

3
3
6
10

示例输出：

17

提示：

参考答案（内存最优[1268]）：

#include <iostream>
#include <cstring>

class CMcNuggets
{
public:
    CMcNuggets();
    ~CMcNuggets();
    void input();
    void output();
    void operate();
private:
    int gcd(int x, int y);
private:
    int m_Num;
    int m_Res;
    int* m_pCnt;
    bool* m_pMark;
    int m_Gcd;
};

CMcNuggets::CMcNuggets()
{
    m_Num = 0;
    m_Res = 0;
    m_Gcd = 0;
    m_pCnt = NULL;
    m_pMark = NULL;
}

CMcNuggets::~CMcNuggets()
{
    if (m_pCnt != NULL)
    {
        delete[] m_pCnt;
        m_pCnt = NULL;
    }
    if (m_pMark != NULL)
    {
        delete[] m_pMark;
        m_pMark = NULL;
    }
}

void CMcNuggets::input()
{
    std::cin >> m_Num;
    m_pCnt = new int[m_Num+1];
    for (int i = 1; i <= m_Num; i++)
    {
        std::cin >> m_pCnt[i];
    }
}

void CMcNuggets::output()
{
    if(m_Gcd != 1)
    {
        std::cout << 0;
    }
    else
    {
        std::cout << m_Res;
    }
    std::cout << std::endl;
}

void CMcNuggets::operate()
{
    m_Gcd = m_pCnt[1];
    for (int i = 2; i <= m_Num; i++)
    {
        m_Gcd = gcd(m_Gcd, m_pCnt[i]);
    }
    if (m_Gcd == 1)
    {
        m_pMark = new bool[100000];
        memset(m_pMark, false, 100000*sizeof(bool));
        m_pMark[0] = true;
        for (int i = 1; i <= 65536; i++)
        {
            for (int j = 1; j <= m_Num; j++)
            {
                if (i >= m_pCnt[j])
                    m_pMark[i] = m_pMark[i] || m_pMark[i-m_pCnt[j]];
            }
        }
        for (int i = 65536; i>= 1;i--)
        {
            if(m_pMark[i] == false)
            {
                m_Res = i;
                break;
            }
        }
    }
}

int CMcNuggets::gcd(int x, int y)
{
    if (x > y)
    {
        int tmp = x;
        x = y;
        y = tmp;
    }
    if (x == 0)
    {
        return y;
    }
    return gcd(y%x, x);
}

int main()
{
    CMcNuggets* pTmp = new CMcNuggets;
    pTmp->input();
    pTmp->operate();
    pTmp->output();
    delete pTmp;
    return 0;
}

参考答案（时间最优[4]）：

#include<cstdio>
#include<iostream>
using namespace std;
int vis[70501];
int a[11];
int n;
int maxsum;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	 {
	 	scanf("%d",&a[i]);
	 	vis[a[i]]=1;
	 }
	 for(int i=1;i<70000;i++)
	 {
	 	if(vis[i]==1)
	 	{
	 		for(int j=0;j<n;j++)
	 		{
				 vis[i+a[j]]=1;
			}
		}
	 }
	 for(int j=70000;j>0;j--)
	   if(vis[j]==0)
	   {
	   	maxsum=j;
	   	break;
	   }
	 for(int i=0;i<n;i++)
	  if(maxsum+a[i]>70000)
	  maxsum=0;
	  printf("%d",maxsum);
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。

退出移动版