主页 / 问题 / 1210340
Accepted
A_Hatake
Asked:2021-11-27 02:49:30 +0000 UTC2021-11-27 02:49:30 +0000 UTC

低点总和

  • 772

给定一个包含 𝑛 整数的数组 𝐴。您需要遍历此数组中的所有数字对𝐴𝑖和𝐴𝑗，为每一对找到最小最小值（𝐴𝑖，𝐴𝑗）并将所有这些最小值相加。输入数据格式：第一行包含一个整数𝑛——数组中有多少个数字（1 <= 𝑁 <= 300 000）。其余的 𝑛 行包含这些数字本身，它们按照它们在数组 𝐴 中出现的顺序排列。所有模数不超过 10^9。输出数据格式：您需要输出一个整数 - 所需的最小值之和 𝑆。𝑆 的总和可能非常大。估计 𝑆 的最大可能值并选择适当的整数类型。需要及时解决问题𝑂(𝑁)。 到目前为止有这样的尝试，但距离 O(N) 还很远：

#include<stdio.h>
int main(){
    int A[300001];
    int N;
    int S; 
    S = 0;
    scanf("%d\n", &N);
    for(int i=1; i<N; i++){
        scanf("%d\n", &A[i]);
    }
    for(int i=1; i<N; i++){
        for(int j=i+1; j!=i; j++){
            if(A[i,j]<=A[i,j+1])
                S=S+A[i,j];
            else
                S=S+A[i,j+1];
        }
    }
    printf("%d", S);
}
c

1 个回答

  1. Best Answer

    具有复杂性的求解方法O(N * log(N))。

    #include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

int main(void)
{
    static int A[300000];
    int N;

    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", &A[i]);

    qsort(A, N, sizeof(int), cmp);

    long long sum_elements = 0;
    long long sum_type_a = 0;
    long long sum_type_b = 0;
    long long sum_type_c = 0;
    for (int i = 0; i < N; ++i)
    {
        sum_type_a += (long long)A[i] * (N - 1 - i);
        sum_type_b += (long long)A[i] * (N - 1 - i) + A[i];
        sum_type_c += (long long)A[i] * (N - 1 - i) + A[i] + sum_elements;
        sum_elements += A[i];
    }

    printf("%lld\n", sum_type_a);
    printf("%lld\n", sum_type_b);
    printf("%lld\n", sum_type_c);
}

    这里有三个总和。
    第一个总和是在假设如果我们考虑了对 的情况下计算的(A[i], A[j])，那么(A[j], A[i])不需要考虑这对。此外，第一个总和不考虑形式对(A[i], A[i])。
    第二个总和与第一个相似，但考虑了形式的对(A[i], A[i])。
    第三个总和类似于第二个，但同时考虑了对(A[i], A[j])和(A[j], A[i])。
    我不知道你需要找到多少...

    在输入

    5
1 2 3 4 5

    将有以下输出：

    20
35
55
    • 1

相关问题