这道题我是用O(1)(应该是)过的。66ms.

先说说大概思路。因为他要尽量买成套的,所以就先用$n/14$记录之后再对$14$取模,接下来要做的就是对余数分类讨论

特别的是,如果n==0,输出3个0,其他的n<3的情况即为无解。

是的,就对于每一个余数分别讨论应该怎么输出。

我们先用一个变量tmp存储下来$n/14$的值,余数记为$p$。

首先,如果没有余数,即p==0,我们就输出三个tmp即可。

当p是3,4,7的整倍数的时候,看起来为了总样数最多,我们要尽可能的买啊!于是当时的思路就是,既然是整数倍,那么就买整数件那个物品。但是!!,因为7=3+4,在余数里面也只会出现7这一个7的倍数,所以我们应该分别购买一件3和一件4!

当p为1,2,5的时候,我们不能直接拼凑出来,所以我们借一组来讨论。即tmp--,p+=14

当p==1,即p==15,我们购买5件3,使总件数最大。

当p==2,即p==16,我们购买4件3+1件4(不是4件4!)使总件数最大。

当p==5,即p==19,我们购买5件3+1件4.

剩下的还有10,11,13

当p==10,我们购买2件3+1件4.

当p==11,我们购买1件3+2件4.

当p==13,我们购买3件3+1件4.

这样打出来就全部完成了


代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
//    freopen("order.in","r",stdin);
//    freopen("order.out","w",stdout);
    int n;
    cin>>n;
    if(!n)
    {
        puts("0 0 0");
        return 0;
     } 
    if(n<3)
    {
        puts("-1");
        return 0;
    }
    int tmp=n/14;
    n%=14;
    if(n==0)
    {
        printf("%d %d %d\n",tmp,tmp,tmp);
        return 0;
    }
    else
    {
        if(n%3==0)
        {
            printf("%d %d %d\n",tmp,tmp,tmp+n/3);
            return 0;
        }
        else if(n%4==0)
        {
            printf("%d %d %d\n",tmp,tmp+n/4,tmp);
            return 0;
        }
        else if(n%7==0)
        {
            printf("%d %d %d\n",tmp,tmp+1,tmp+1);
            return 0;
        }
        else if(n==1)
        {
            if(tmp)
            {
                tmp--;
                printf("%d %d %d\n",tmp,tmp,tmp+5);
            }
            else puts("-1");
            return 0;
        }
        else if(n==2)
        {
            if(tmp)
            {
                tmp--;
                printf("%d %d %d\n",tmp,tmp+1,tmp+4);
            }
            else puts("-1");
            return 0;
        }
        else if(n==5)
        {
            if(tmp)
            {
                tmp--;
                printf("%d %d %d\n",tmp,tmp+1,tmp+5);
            }
            else puts("-1");
            return 0;
        }
        else if(n==10)
        {
            printf("%d %d %d\n",tmp,tmp+1,tmp+2);
            return 0;
        }
        else if(n==11)
        {
            printf("%d %d %d\n",tmp,tmp+2,tmp+1);
            return 0;
        }
        else if(n==13)
        {
            printf("%d %d %d\n",tmp,tmp+1,tmp+3);
            return 0;
        }
    }
    return 0;
}
最后修改:2020 年 04 月 10 日 05 : 46 PM