[HNOI2002]营业额统计

NC20026. [HNOI2002]营业额统计

描述

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。
经济管理学上定义了一种最小波动值来衡量这种情况：记该天以前某一天的营业额为 $a_i$ ，该天营业额为b，则该天的最小波动值 $\delta= \min|a_i-b|$ ，当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。
你的任务就是编写一个程序帮助Tiger来计算这一个值，第一天的最小波动值为第一天的营业额。
一句话题意

给出一个n个数的数列 $\{a_n \}$ ，对于第i个元素 $a_i$ ，定义 $f_i= \min|a_i-a_j|$ ，其中 $1 \leq j \lt i,f_1=a_1$ 。求 $\sum f_i$ 。

输入描述

第一行为正整数，表示该公司从成立一直到现在的天数；
接下来的n行每行有一个正整数，表示第i天公司的营业额。

输出描述

仅有一个正整数，即每一天最小波动的和，结果不超过。

示例1

输入:

输出:

说明:

5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang11) 解法, 执行用时: 381ms, 内存消耗: 580K, 提交时间: 2020-12-21 21:20:46

#include<stdio.h>
#include<math.h>
int main()
{
    int n,i,a[1000001],j,k,sum,min;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    sum=a[0];
    for(i=1;i<n;i++)
    {
        min=abs(a[i]-a[0]);
        for(j=1;j<i;j++)
            if(abs(a[i]-a[j])<min)
                min=abs(a[i]-a[j]);
        sum+=min;
    }
    printf("%d\n",sum);
}

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 858ms, 内存消耗: 572K, 提交时间: 2023-06-16 21:12:16

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MAXN 50005
int a[MAXN], n;
ll ans;
int main()
{
	cin >> n >> a[1];
	ans = a[1];
	for(int i = 2; i <= n; i++) {
		int res = 1e9;
		cin >> a[i];
		for(int j = 1; j < i; j++) {
			res = min(res, abs(a[i] - a[j]));
		}
		ans += res;
	}
	
	cout << ans << endl;
}

C++(clang++11) 解法, 执行用时: 169ms, 内存消耗: 540K, 提交时间: 2022-07-28 14:17:00

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	int a[40000];
	cin>>n;
	for(int i=0;i!=n;i++)
	cin>>a[i];
    long ans=a[0];
	for(int i=1;i!=n;i++)
	{
		int smin;
		smin=2100000000;
		for(int j=0;j<i;j++)
		smin=min(smin,abs(a[i]-a[j]));
		ans+=smin;
	}
	cout<<ans;
}