欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Moo Volume

程序员文章站 2022-05-21 08:18:35
...

Moo Volume

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 6   Accepted Submission(s) : 2
Problem Description
Farmer John has received a noise complaint from his neighbor, Farmer Bob, stating that his cows are making too much noise. 

FJ's N cows (1 <= N <= 10,000) all graze at various locations on a long one-dimensional pasture. The cows are very chatty animals. Every pair of cows simultaneously carries on a conversation (so every cow is simultaneously MOOing at all of the N-1 other cows). When cow i MOOs at cow j, the volume of this MOO must be equal to the distance between i and j, in order for j to be able to hear the MOO at all. Please help FJ compute the total volume of sound being generated by all N*(N-1) simultaneous MOOing sessions.
 

Input
* Line 1: N <br> <br>* Lines 2..N+1: The location of each cow (in the range 0..1,000,000,000).
 

Output
There are five cows at locations 1, 5, 3, 2, and 4.
 

Sample Input

5 1 5 3 2 4
 

Sample Output

40
 

Source
PKU

 题目大意:
数轴上共有N头牛,每头牛有一个坐标。每头牛都要向其他所有牛发出一个叫声,因此一共有 N*(N-1) 个叫声。
每个叫声的大小等于两头牛之间坐标差的绝对值。输出所有叫声大小的和。

思路:
只计算单向距离,最后结果乘以2即可

如:1 2 3 4 5   (这里代表的是点的序号)

以 2-3 这一段为例, 1 ( 2 - 3 ) 4 5

计算2-3这一段在总的距离中出现的次数,因为只有跨越2-3这一段的长度才包含这一段,从1到3、4、5,2到3、4、5都包含这一段,可以得出这一段出现的次数为该段左侧的点数乘右侧的点数,以上计算的只是从左侧端点到右侧端点的次数,由于是双向的,反过来的结果是等效的,所以最后还要乘2

设当前一段的端点为a[i]和a[i+1],则这一段出现的次数表达式为:i * ( n - i ) * 2

题目中要求的是距离的总和,把每一段出现的次数乘该段的长度再求和即可

sum = sum+( ( a[i+1] - a[i] ) * i * ( n - i ))   ( i = 1, 2, ..., n )

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
long long  a[10002];

int main(){
	int  n;
	while(scanf("%d",&n)!=EOF){
	
	memset(a,0,sizeof(a));

	
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);	
	}
	sort(a,a+n);
		
	long long sum=0;

	for(int i=1;i<n;i++)
	{		
		sum+=(a[i]-a[i-1])*i*(n-i);
	}
	
	printf("%lld\n",sum*2);
				
	}

}