a066 - HNOI2002 营业额统计
題目描述
題目要求計算公司成立以來每一天的最小波動值之和。最小波動值定義為該天以前某一天的營業額與該天營業額的絕對差的最小值。第一天的最小波動值為第一天的營業額。
解題思路
對於每一天，我們需要找到之前所有天數的營業額與當天營業額的絕對差的最小值。可以使用迴圈遍歷之前的所有天數，計算絕對差，並更新最小值。將每一天的最小波動值累加起來，即可得到最終結果。為了避免重複計算，可以使用一個布林陣列 b 記錄已經處理過的非負數營業額，如果當天營業額是非負數且已經在 b 陣列中標記，則跳過。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int a[32768],b[1000001]={0};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,ans=0;
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i];
if(a[i]>=0&&b[a[i]])
continue;
int tmp=1000001;
if(i==0)tmp=a[0];
for(int j=0;j<i&&tmp;++j)
tmp=min(abs(a[i]-a[j]),tmp);
ans+=tmp;
if(a[i]>=0)b[a[i]]=1;
}
cout << ans << '\n';
}