珂爱的萌新TLE求助

P6188 [NOI Online #1 入门组] 文具订购

wwhOvO @ 2020-03-11 21:50:06

感觉有用的优化都用上了啊QAQ还是只有90分。。。

请问哪里还要优化啊QAQ

#include <iostream>
#include <stdio.h>
#include <math.h>
#define DEBUG printf("aa/7=%d bb/4=%d cc/3=%d\n",aa/7,bb/4,cc/3)
#define DEBUG2 printf("a=%d b=%d c=%d\n\n",a,b,c)
#define DEBUG3 printf("aa=%d bb=%d cc=%d\n",aa,bb,cc)

using namespace std;

int n,a,b,c;

int main()
{
    //freopen("order.in","r",stdin);
    //freopen("order.out","w",stdout);
    scanf("%d",&n);
    if(n==3) {printf("0 0 1\n");return 0;}
    if(n==4) {printf("0 1 0\n");return 0;}
    if(n==7) {printf("0 1 1\n");return 0;}
    if(n%14==0)
    {
        a=b=c=(n/14);
        printf("%d %d %d\n",a,b,c);
        return 0;
    }

    for(int i=1;i<=n/3;i++)
    {
        int aa,bb,cc=i*3;
        int can=n-cc;
        for(int j=1;j<=can/4;j++)
        {
            int nans=a+b+c;
            int minn=min(min(a,b),c);
            //cout<<minn<<endl;
            bb=j*4;
            aa=n-(bb+cc);
            //DEBUG3;
            if((aa+bb+cc==n)&&(aa%7==0)&&(aa>=0))
            {
                int now=min(min(aa/7,bb/4),cc/3);
                //DEBUG;
                //if(a==0&&b==0&&c==0) {a=aa/7,b=bb/4,c=cc/3;continue;}
                if(now>=minn)
                {
                    //DEBUG;
                    //cout<<"now="<<now<<endl;
                    //cout<<minn<<endl;
                    int ans=(aa/7)+(bb/4)+(cc/3);
                    //cout<<"ans="<<ans<<" "<<"nans="<<nans<<endl;
                    //cout<<"a="<<a<<" "<<"b="<<b<<" "<<"c="<<c<<endl;
                    if(ans>=nans) {a=aa/7,b=bb/4,c=cc/3;continue;}
                    //cout<<"Get a answer:"<<"a="<<a<<" "<<"b="<<b<<" "<<"c="<<c<<endl;
                    //<<"-------------------\n";
                    if(now!=minn) a=aa/7,b=bb/4,c=cc/3;
                }
            }
        }
    }
    if(a==0&&b==0&&c==0) printf("-1\n");
    else printf("%d %d %d\n",a,b,c);
    return 0;
}

by answerend42 @ 2020-03-11 21:52:10

@BinaryTree 这一题是O(1)的结论题,那么复杂干什么啊?


by kevin516 @ 2020-03-11 21:52:58

开O2


by 123456zmy @ 2020-03-11 21:53:42

把这个扔到代码前面,再把O2优化勾上


by wwhOvO @ 2020-03-11 21:53:50

@answerend42 不会,因为有人和我几乎一样的代码A了。。。就很烦,,唯一一道比较会做的题还写挂了/kk


by wwhOvO @ 2020-03-11 21:54:52

@kevin516 开02还是95分啊/jk


by wwhOvO @ 2020-03-11 21:56:55

@123456zmy 这个考试能不能用啊qwq


by liqingyang @ 2020-03-11 21:57:19

@BinaryTree 加register


by liqingyang @ 2020-03-11 21:57:48

@BinaryTree 还有不要用algorithm库的min,太慢了


by liqingyang @ 2020-03-11 21:58:43

@BinaryTree 然后实在不行把算多遍的东西保存起来,例如:aa/7等等


by liqingyang @ 2020-03-11 21:59:17

@BinaryTree 这些都是运算次数较多时的常识


| 下一页