題目：

?Problem 1492 地震預測

Accept: 354????Submit: 1902
Time Limit: 1500 mSec????Memory Limit : 32768 KB

?Problem Description

懷特先生是一名研究地震的科學家，最近他發現如果知道某一段時間內的地殼震動能量采樣的最小波動值之和，可以有效地預測大地震的發生。

假設已知一段時間的n次地殼震動能量的采樣值為a₁,a₂,…a_n，那么第i 次采樣的最小波動值為min{|a_i-a_j| | i<j<=n}，即第i 次采樣的最小波動值是其后n-i次采樣值與第i次采樣值之差的絕對值中最小的值，特別地，第n次采樣的最小波動值為a_n。

請編寫一個程序計算這n次采樣的最小波動值之和。

?Input

本題有多組輸入數據，你必須處理到EOF為止

輸入數據第一行有一個數n(1<=n<=10⁵) ,表示采樣的次數。

第二行有n個整數，表示n次地殼震動能量的采樣值a₁,a₂,…a_n?(0<=a_i<=10⁷?)。

?Output

輸出n次采樣的最小波動值之和。

?Sample Input

42 0 3 10

?Sample Output

21

?Source

福州大學第四屆程序設計競賽
Submit??Back??Status??Discuss 思路：

用數組模擬鏈表，先用結構體記錄數字和當前的位置，再排序所以它與它后面的所有數的最小值就是它與它旁邊兩個數比較的最小值。

等到比較過后，刪除當前的節點。最后再輸出節點

代碼：

#include <stdio.h> #include <string.h> #include <string> #include <iostream> #include <stack> #include <cmath> #include <queue> #include <vector> #include <algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define N 100000+20 #define M 1000000+10 #define LL long long using namespace std; const int inf=2e9+10; int n,pre[N],next[N],ff[N]; struct node {int x,po; }zz[N]; bool cmp(node a,node b) {return a.x<b.x; } int find(int i) {return min(abs(zz[i].x-zz[pre[i]].x),abs(zz[i].x-zz[next[i]].x));//排好序以后返回離他最近的值 } void del(int i)//刪除節點 {pre[next[i]]=pre[i];next[pre[i]]=next[i]; }int main() {while(~scanf("%d",&n)){zz[0].x=-inf;zz[n+1].x=inf;for(int i=1;i<=n;i++){scanf("%d",&zz[i].x);zz[i].po=i;}int ans=zz[n].x;//要加上最后一個值sort(zz+1,zz+n+1,cmp);for(int i=1;i<=n;i++){ff[zz[i].po]=i;//原順序的第i位，在排好序的第ff[i]位pre[i]=i-1;//記錄左右節點next[i]=i+1;}for(int i=1;i<=n-1;i++){ans+=find(ff[i]);//加上絕對值最小的del(ff[i]);}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的FZU1492 地震预测(链表模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。