大佬求解这道题，求代码

这道题怎么做，差分数组，求附代码，c++编程

 

 

1.题目描述

Farmer John因为他的奶牛发出的声音太大而被他的邻居Bob投诉。

FJ的N(1≤N≤100000)头奶牛都在牧场上的不同位置上吃草，牧场可以看做是一个长的一维牧场。奶牛们非常健谈，每对奶牛同时进行对话，所以每头奶牛同时与其他N-1头奶牛发哞哞声。当奶牛i对奶牛j发出哞哞声时，这个哞哞声的音量必须等于i和j之间的距离，这样奶牛j才能听到哞哞声。

请帮助FJ计算N*(N-1)个哞哞声同时发声时产生的声音总量。

输入格式

第一行，一个整数N，表示奶牛的数量

接下来N行，每行一个整数，表示N头奶牛在牧场上的位置Li（0≤Li≤10^8）

输出格式

一个整数，表示总音量

输入输出样列

输入样例1：

 
5 1 5 3 2 4

输出样例1：

 
40

说明

样例说明：

5头奶牛的位置分别是：1,5,3,2,4

位置1的奶牛产生的音量是 1+2+3+4=10, 

位置5的奶牛产生的音量是 4+3+2+1=10, 

位置3的奶牛产生的音量是 2+1+1+2=6, 

位置2的奶牛产生的音量是 1+1+2+3=7, 

位置4的奶牛产生的音量是 3+2+1+1=7. 

所以总的音量是(10+10+6+7+7) = 40.


#include <stdio.h>

#define ARRAY_SIZE 100000

int input_sounds(int sound[ARRAY_SIZE])
{
    int number_of_sound = 0;
    char text[ARRAY_SIZE * 10];
    int i;
    
    printf("Please enter the number of sound values, followed by sound values, delimited by spaces or linebreaks:\n");
    scanf("%d", &number_of_sound);
    
    for (i = 0; i < number_of_sound; ++i)
        scanf("%d", &sound[i]);
    
    return number_of_sound;
}

unsigned long long calculate_total_sound(int sound[ARRAY_SIZE], int number_of_sound)
{
    unsigned long long total_sound = 0;
    int i, j;
    
    for (i = 0; i < number_of_sound; ++i)
        for (j = 0; j < number_of_sound; ++j)
            if (i != j)
            {
                int sound_to_hear = sound[i] - sound[j];
                if (sound_to_hear < 0)
                    sound_to_hear = -sound_to_hear;
                total_sound += sound_to_hear;
            }

    return total_sound;
}

int main()
{   
    int sound[ARRAY_SIZE];
    int number_of_sound = 0;
    unsigned long long total_sound = 0;

    number_of_sound = input_sounds(sound);
    
    total_sound = calculate_total_sound(sound, number_of_sound);
    printf("The total sound is %lld\n", total_sound);

    return 0;
}


// Output:
Please enter the number of sound values, followed by sound values, delimited by spaces or linebreaks:
5 1 5 3 2 4
The total sound is 40

 

您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~

如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～

ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632


#include<bits/stdc++.h>
using namespace std;
const int N=100005;
long long n,ans,x[N],d[N],l[N],r[N];
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &x[i]);
    sort(x+1,x+1+n);
    //计算牛i到其左边所有牛的距离和
    for(int i=1;i<=n;i++){
        l[i]=l[i-1] + (i-1) * (x[i]-x[i-1]);
        ans+=l[i];
    }
    //计算牛i到其右边所有牛的距离和
    for(int i=n;i>=1;i--){
        r[i]=r[i+1] + (n-i) * (x[i+1]-x[i]);
        ans+=r[i];
    }
    printf("%lld",ans);
    return 0;
}

设：x[i]记录第i头牛的位置
设：l[i]记录第i头牛到其左边所有牛的距离和
设：r[i]记录第i头牛到其右边所有牛的距离和
则① l[i] = l[i-1] + (i-1) (x[i]-x[i-1]);
② rli] = rli+1] + (n-i)(x[i+1]-x[i]);
输入的位置是无序的，需要进行排序*

img