为什么都超时。。。弱鸡求助

helpcyg @ 2020-06-03 21:23:23

#include<iostream>
using namespace std;
bool same(int A[],int B[],int C[]){
    int times = A[0]*A[1]*A[2]*B[0]*B[1]*B[2]*C[0]*C[1]*C[2],plus = A[0]+A[1]+A[2]+B[0]+B[1]+B[2]+C[0]+C[1]+C[2];
    if((times == 362880)&&(plus == 45)){
        return false;
    }
    return true;
}
int main(){
    int one,two,three,count = 0;
    cin>>one>>two>>three;
    for(int i = 123;i < 988;i++){
        for(int j = i + 1;j < 988;j++){
            for(int h = j + 1;h < 988;h++){
                int a[3],b[3],c[3];
                a[0] = i % 10;
                a[1] = i / 10 % 10;
                a[2] = i / 100;

                b[0] = j % 10;
                b[1] = j / 10 % 10;
                b[2] = j / 100;

                c[0] = h % 10;
                c[1] = h / 10 % 10;
                c[2] = h / 100;     
                if(j % i == 0 && h % i == 0){
                    if((j / i == two && h / i == three) && (!same(a,b,c))){
                        cout<<i<<" "<<j<<" "<<h<<endl;
                        count++;
                    }
                }
            }
        }
    }
    if(count == 0){
        cout<<"No!!!";
    }
    return 0;
}

by 囧仙 @ 2020-06-03 21:25:20

@helpcyg ……建议学一下时间复杂度。

by 警策看取 @ 2020-06-03 21:25:27

那是肯定的

by iMya_nlgau @ 2020-06-03 21:25:44

next_permutation 不香吗 = =

by helpcyg @ 2020-06-03 21:25:56

我学生，没学过，我老师叫我做

by helpcyg @ 2020-06-03 21:27:05

有没有能优化的地方？

by 菜鸡gyf @ 2020-06-03 21:27:50

九个循环比三个循环好！

by infinities @ 2020-06-03 21:29:37

啊这，复杂度得爆啊，一堆乘除取模常数得近百了/jk

by twelveZ @ 2020-06-03 21:29:39

@helpcyg 改成九个循环

#include <stdio.h>
#include <cstdlib>
#include<iostream>
using namespace std;

int main()
{
int a1,a2,a3;
bool flag=0;
cin>>a1>>a2>>a3;
    int i[9];
    for (i[0] = 1; i[0] <= 9; i[0]++)
    {
        for (i[1] = 1; i[1] <= 9; i[1]++)
        {
            int p1=0;
            if (i[1] == i[0]) p1 = 1;
            if (p1 != 1) {
                for (i[2] = 1; i[2] <= 9; i[2]++)
                {
                    int p2=0;
                    for (int j2 = 0; j2 < 2; j2++) if (i[2] == i[j2]) p2 = 2;
                    if (p2 != 2) {
                        for (i[3] = 1; i[3] <= 9; i[3]++)
                        {
                            int p3=0;
                            for (int j3 = 0; j3 < 3; j3++) if (i[3] == i[j3]) p3 = 3;
                            if (p3 != 3) {
                                for (i[4] = 1; i[4] <= 9; i[4]++)
                                {
                                    int p4=0;
                                    for (int j4 = 0; j4 < 4; j4++) if (i[4] == i[j4]) p4 = 4;
                                    if (p4 != 4) {
                                        for (i[5] = 1; i[5] <= 9; i[5]++)
                                        {
                                            int p5=0;
                                            for (int j5 = 0; j5 < 5; j5++) if (i[5] == i[j5]) p5 = 5;
                                            if (p5 != 5) {
                                                for (i[6] = 1; i[6] <= 9; i[6]++)
                                                {
                                                    int p6=0;
                                                    for (int j6 = 0; j6 < 6; j6++) if (i[6] == i[j6]) p6 = 6;
                                                    if (p6 != 6) {
                                                        for (i[7] = 1; i[7] <= 9; i[7]++)
                                                        {
                                                            int p7=0;
                                                            for (int j7 = 0; j7 < 7; j7++) if (i[7] == i[j7]) p7 = 7;
                                                            if (p7 != 7) {
                                                                for (i[8] = 1; i[8] <= 9; i[8]++)
                                                                {
                                                                    int p8=0;
                                                                    for (int j8 = 0; j8 < 8; j8++) if (i[8] == i[j8]) p8 = 8;
                                                                    if (p8 != 8) {
                                                                        int a = 100 * i[0] + 10 * i[1] + i[2];
                                                                        int b = 100 * i[3] + 10 * i[4] + i[5];
                                                                        int c = 100 * i[6] + 10 * i[7] + i[8];
                                                                      if (a/a1==b/a2&&b/a2==c/a3&&c/a3==a/a1&&a%a1==0&&b%a2==0&&c%a3==0) {cout<<a<<" "<<b<<" "<<c<<endl;flag=1; }                                                                  } 

                                                                       }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }

    }
    if (flag==0) cout<<"No!!!";
    return 0;
}

by 一只书虫仔 @ 2020-06-03 21:31:26

咋了，我们不都是学生吗（

by 一只书虫仔 @ 2020-06-03 21:32:01

建议去 OI-Wiki 学习时间复杂度