Очистка тестовых случаев конкурентного алогита

Question

Я застрял в очистке всех тестовых примеров для простого алгоритма, и я ищу причины или модификации, которые я должен сделать в своем коде. Здесь есть встроенная ссылка на вопрос.

Вероятным решением может быть сортировка двух массивов с последующим добавлением соответствующих терминов, но оно не завершает все тестовые случаи.

#include <stdio.h>
#include <assert.h>
int main() {
    long long n, i;

    scanf("%lld", &n);
    if (!(n >= 1 && n <= 1000000))
        exit(1);

    long long s[n], c[n], sum = 0, temp = 0, j;

    // taking input for cat and strength array
    for (i = 0; i < n; i++) {
        scanf("%lld", &s[i]);

        if (!(s[i] >= 1 && s[i] <= 1000000))
            exit(1);
    }
    for (i = 0; i < n; i++) {
        scanf("%lld", &c[i]);
        if (!(c[i] >= 1 && c[i] <= 1000000))
            exit(1);
    }

    // Sorting the C array
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (c[i] > c[j]) {
                temp = c[i];
                c[i] = c[j];
                c[j] = temp;
            }
        }
    }

    // sorting the S array
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (s[i] > s[j]) {
                temp = s[i];
                s[i] = s[j];
                s[j] = temp;
            }
        }
    }

    // Finally adding up the sorted elements
    for (i = 0; i < n; i++) {
        sum = sum + (s[i] * c[i]);
    }

    printf("%d ", sum);
    getch();
}

Answer 1

1. Чтобы избежать ошибок во время выполнения, объявите массивы с большим размером (1e6) в глобальной области видимости.
2. Чтобы избежать превышения лимита времени, обратите внимание, что используемая сортировка занимает O(N^2) времени, поэтому для массива с размером 1e6 сортировка в худшем случае занимает до 1e12(приблизительных) вычислительных операций. Стандартные алгоритмы сортировки (сортировка слиянием, быстрая сортировка) занимают время O(NlgN), что намного лучше, чем текущий подход, и как c[i], s[i] <= 1e6 Вы даже можете сортировать массивы по линейному времени.
3. Ох и преодолеть Wrong answersзаменить printf("%d ",sum); с printf("%lld ",sum); сумма является переменной типа long long

Answer 2

Обратите внимание, что n <= 10^6, Ваш алгоритм имеет O(n^2) сложность времени. Это слишком медленно. Вам определенно нужно использовать более эффективный алгоритм сортировки. Например, вы можете использовать qsort от stdlib.h,