欢乐赛#67 T3 题解

题目大意

@skirmish 现在正在进行车辆测试，给定采样点的高度 $h_1,h_2\dots h_n$，定义从点 $i\ (1\le i<n)$ 到点 $i+1$ 的颠簸量 $d_i$ 为 $|h_{i+1}-h_i|$，求所有相邻段颠簸量的平均值。

解题思路

由题意可得：$d_1=|h_2-h_1|,d_2=|h_3-h_2|,\dots,d_{n-1}=|h_n-h_{n-1}|$。没有 $d_n$。

题目求的是 $\dfrac{d_1+d_2+\cdots+d_{n-1}}{n-1}$，所以答案为：

$$\dfrac{h_2-h_1|+|h_3-h_2|+\cdots+|h_n-h_{n-1}|}{n-1}$$

Code

时间复杂度：$\text O(n)$。

#include <bits/stdc++.h>
using namespace std;
int n;
long long h[100005];
long long avg;//见祖宗
int main(){
	cin>>n;
    for (int i=1;i<=n;i++){
        cin>>h[i];
        if (i-1){//即i>1
            avg+=fabs(h[i]-h[i-1]);
        }
    }
    printf("%.2lf",avg*1.0/(n-1));//必须要 *1.0，否则两个整数相除结果向下取整
	return 0;
}