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.
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);
}
}
上一篇: P1048 采药
下一篇: 6.30 使用枚举类代替常量