20分求助

SIXIANG32 @ 2020-03-08 11:53:44

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n=1000000,z;
    cin>>n;
    for(int p=n/3;p>=1;p--)//一共可以买多少笔记本 
        for(int i=n/4;i>=1;i--)//一共可以买多少笔 
            {
                z=(n-(p*3)-(i*4))/7;
                if(z*7+p*3+i*4==n&&z>0&&i>0&&p>0)
                {
                    cout<<z<<' '<<i<<' '<<p<<endl;
                    return 0;
                }
            }
    cout<<-1;
    return 0;
}

by _JEB_ @ 2020-03-08 12:07:55

在满足以上条件情况下，成套的数量尽可能大，即 a,b,c 中的最小值尽可能大。
在满足以上条件情况下，物品的总数尽可能大，即 a+b+c 尽可能大。

这两个特判你没写

by SIXIANG32 @ 2020-03-08 12:07:59

@Charlie___j 坑能

by IntrepidStrayer @ 2020-03-08 12:08:40

@SIXIANG dfs

#include <cstdio>
using namespace std;
int price[4] = {0, 3, 4, 7}, ans[4], n;
bool dfs(int money, int id) {
    if(id == 3) {
        if(money % 7 == 0) {
            ans[3] = money / 7;
            return true;
        }
        else return false;
    }
    for(ans[id] = money / price[id]; ans[id] >= 0; --ans[id])
        if(dfs(money - price[id] * ans[id], id + 1))
            return true;
    return false;
}
signed main() {
    scanf("%d", &n);
    for(int qwq = n / 14; qwq >= 0; --qwq)
        if(dfs(n - qwq * 14, 1)) {
            printf("%d %d %d\n", ans[3] + qwq, ans[2] + qwq, ans[1] + qwq);
            return 0;
        }
    printf("-1\n");
    return 0;
}

by SIXIANG32 @ 2020-03-08 12:09:30

@fhh_orz ORZORZORZORZORZ

by IntrepidStrayer @ 2020-03-08 12:10:01

你那样会T

by IntrepidStrayer @ 2020-03-08 12:10:34

#include <cstdio>
using namespace std;
int num[15]={0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0};
int x[15]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int y[15]={0, 0, 1, 0, 1, 1, 0, 1, 2, 0, 1, 2, 0, 1};
int z[15]={0, 5, 4, 1, 0, 5, 2, 1, 0, 3, 2, 1, 4, 3};
int main() {
    //freopen("order.in", "r", stdin);
    //freopen("order.out", "w", stdout);
    int n, qwq, tql;
    scanf("%d", &n);
    if(n % 14 == 0) {
        printf("%d %d %d\n", n/14, n/14, n/14);
        return 0;
    }
    qwq = n / 14;
    tql = n % 14;
    if(qwq < num[tql]) {
        printf("-1\n");
        return 0;
    }
    qwq -= num[tql];
    printf("%d %d %d\n", x[tql] + qwq, y[tql] + qwq, z[tql] + qwq);
    return 0;
}

by _JEB_ @ 2020-03-08 12:10:50

@SIXIANG

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;//n元钱 
int ansa,ansb,ansc;//答案(最优)的 a b c 
int mnans,mntmp;//最优答案的最小值 和  新鲜出炉的 a b c 的最小值 
int totans,tottmp;//最优答案的个数总和 和 新鲜出炉的 a b c 的总和 
bool flag;//判断有没有合法解 
inline void read(int &x)//快读 
{
    int f;char c;
    for (f=1,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for (x=0;c<='9'&&c>='0';c=getchar()) x=x*10+(c&15);x*=f;
}
inline int mn(int _x,int _y)
{
    return _x<_y?_x:_y;
}
inline int mx(int _x,int _y)
{
    return _x>_y?_x:_y;
}
inline int ab(int _x)
{
    if(_x<0) return -_x;
    else return _x;
}
int main()
{
//  freopen("order.in","r",stdin);//为文件输入输出 
//  freopen("order.out","w",stdout);
    ansa=ansb=ansc=-1;//初始化肯定是最小 -1 就够了 
    totans=-3;
    mnans=-1;
    read(n);//读入 
    for(int a=0;a*7<=n;a++)//第一层循环 求 a 
    {
        int upb=n-7*a;//求出 b 的上限 
        for(int b=0;b*4<=upb;b++)//再枚举 b 
        {
            int c=n-7*a-4*b;//算一下c 但并没有除3 
            if(c%3!=0) continue;//看看是不是整数 
            flag=true;//到这里就有合法解了 
            c/=3;//最后的c是要除3的 
            mntmp=mn(mn(a,b),c);//新鲜出炉的 a b c的最小值 
            if(mntmp>=mnans)//题目条件1 
            {
                if(mntmp>mnans)//不用继续比较条件2了 
                {
                    ansa=a;//更新 
                    ansb=b;
                    ansc=c;
                    mnans=mntmp;
                    totans=a+b+c;
                }
                else//在比较条件2 
                {
                    tottmp=a+b+c;//新鲜出炉的 a b c的总和 
                    if(tottmp>totans)//更优解 
                    {
                        ansa=a;//更新 
                        ansb=b;
                        ansc=c;
                        mnans=mntmp;
                        totans=tottmp;
                    }
                }
            }
        }
    }
    if(flag) printf("%d %d %d\n",ansa,ansb,ansc);//有解输出最优的 
    else printf("-1\n");//没有就-1呗 
    return 0;
}

看看这个 和我思路差不多

by _JEB_ @ 2020-03-08 12:11:41

orz

@fhh_orz

by SIXIANG32 @ 2020-03-08 12:12:08

@Charlie___j 谢谢

by IntrepidStrayer @ 2020-03-08 12:13:06

@Charlie___j 不会TLE吗？100000时1778ms