P2234 营业额统计

题目原文及输入/输出格式

题目描述

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。

第一天的最小波动值为第一天的营业额。

该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。

20分解法——纯模拟

根据题目提供的公式：该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}，遍历该天之前的营业额求最小波动值。

每一次遍历求解的时间复杂度是$O(n)$，程序时间复杂度是$O(n^2)$

long long n, U[32780];
long long ans;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>U[i];
	for(int i=1;i<=n;i++){
		if(i==1){
			ans+=U[i];
			continue;
		}
		
		long long minn=LLONG_MAX;
		for(int j=i-1;j>=1;j--){
			minn=min(minn, abs(U[i]-U[j]));
		}
		ans+=minn;
	}
	cout<<ans;
	return 0;
}

优化解法

to be continued