391
HNOI 2002 營業額統計 Splay解法
地址：https://www.lydsy.com/JudgeOnline/problem.php?id=1588
題意：Tiger 最近被公司升任為營業部經理，他上任後接受公司交給的第一項任務便是統計並分析公司成立以來的營業情況。Tiger 拿出了公司的賬本，賬本上記錄了公司成立以來每天的營業額。分析營業情況是一項相當複雜的工作。由於節假日，大減價或者是其他情況的時候，營業額會出現一定的波動，當然一定的波動是能夠接受的，但是在某些時候營業額突變得很高或是很低，這就證明公司此時的經營狀況出現了問題。經濟管理學上定義了一種最小波動值來衡量這種情況，最小波動值= min { | 該天以前某一天的營業額-該天的營業額| }，求最小波動值的和。注：第一天的最小波動值為第一天的營業額。
數據範圍：天數n≤32767，每天的營業額ai≤1,000,000。最後結果T≤2^31。
進一步分析本題，解題中，涉及到對於有序集的三種操作：插入、求前趨、求後繼。而對於這三種操作，伸展樹的時間複雜度都非常優秀，於是我們設計了如下算法：開始時，樹S 為空，總和T 為零。每次讀入一個數p，執行Insert(p,S)，將p插入伸展樹S。這時，p 也被調整到伸展樹的根節點。這時，求出p 點左子樹中的最右點和右子樹中的最左點，這兩個點分別是有序集中p的前趨和後繼。然後求得最小差值，加入最後結果T。
/**************************************************************
Problem: 1588
User: h6363817
Language: C++
Result: Accepted
Time:168 ms
Memory:16896 kb
****************************************************************/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mm=1000005;
const int oo=1e9;
struct SplayTree
{
int son[mm][2],far[mm],val[mm];
int rt,size;
void Link(int x,int y,int c)
{
//將x作為y的c兒子連接上
far[x]=y,son[y][c]=x;
}
void Rotate(int x,int c)
{
//c=0則x是y的左兒子
int y=far[x];
Link(x,far[y],son[far[y]][1]==y);
Link(son[x][!c],y,c);
Link(y,x,!c);
}
void Splay(int x,int g)
{
for(; far[x]!=g;)
{
int y=far[x],cy=(son[far[y]][1]==y),cx=(son[y][1]==x);
if(far[y]==g)Rotate(x,cx);
else
{
if(cx==cy)Rotate(y,cy);
else Rotate(x,cx);
Rotate(x,cy);
}
}
if(!g)rt=x;
}
void NewNode(int y,int &x,int a)
{
x=++size;
far[x]=y,val[x]=a;
son[x][0]=son[x][1]=0;
}
void Prepare()
{
NewNode(size=0,rt,-oo);
NewNode(rt,son[rt][1],oo);
}
void Insert(int a)
{
int x=rt;
while(son[x][val[x]<a])x=son[x][val[x]<a];
NewNode(x,son[x][val[x]<a],a);
Splay(size,0);
}
int Pre(int a)
{
int x=rt,ret=-oo;
while(x)
{
if(val[x]==a)return a;
if(val[x]<a)ret=max(ret,val[x]);
x=son[x][val[x]<a];
}
return ret;
}
int Suc(int a)
{
int x=rt,ret=oo;
while(x)
{
if(val[x]==a)return a;
if(val[x]>a)ret=min(ret,val[x]);
x=son[x][val[x]<a];
}
return ret;
}
} spt;
int main()
{
int n,a,t;
scanf("%d%d",&n,&a);
t=a;
spt.Prepare();
spt.Insert(a);
while(--n)
{
if(scanf("%d",&a)==-1) a=0;
t+=min(a-spt.Pre(a),spt.Suc(a)-a);
spt.Insert(a);
}
printf("%d\n",t);
return 0;
}
最後更新：2017-04-03 16:48:56