「BZOJ1588」[HNOI2002] 营业额统计

2014年3月28日8,5873

Description

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

Input

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

Output

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

Sample Input

6
5
1
2
5
4
6

Sample Output

HINT

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

代码

双向链表（本题参考论文《基本数据结构在信息学竞赛中的应用》）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct data{
    int p,v;
    int left,right;
}a[40001];
inline bool cmp(data a,data b){return a.v<b.v;}
int n,rank[40001];//排序后每个点的位置
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].v);
        a[i].p=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)rank[a[i].p]=i;
    for(int i=1;i<=n;i++)
    {
        a[i].left=i-1;
        a[i].right=i+1;
    }
    a[n].right=0;
    int ans=a[rank[1]].v;
    for(int i=n;i>1;i--)
    {
        int x=rank[i];
        if(a[x].left&&a[x].right)
        {
        ans+=min(a[x].v-a[a[x].left].v,a[a[x].right].v-a[x].v);
        a[a[x].left].right=a[x].right;
        a[a[x].right].left=a[x].left;
        }
        else if(!a[x].left)
        {
             ans+=a[a[x].right].v-a[x].v;
             a[a[x].right].left=0;
             }
        else
        {
             ans+=a[x].v-a[a[x].left].v;
             a[a[x].left].right=0;
            }
    }
    printf("%d",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

struct data{

int p,v;

int left,right;

}a[40001];

inline bool cmp(data a,data b){return a.v<b.v;}

int n,rank[40001];//排序后每个点的位置

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i].v);

a[i].p=i;

}

sort(a+1,a+n+1,cmp);

for(int i=1;i<=n;i++)rank[a[i].p]=i;

for(int i=1;i<=n;i++)

{

a[i].left=i-1;

a[i].right=i+1;

}

a[n].right=0;

int ans=a[rank[1]].v;

for(int i=n;i>1;i--)

{

int x=rank[i];

if(a[x].left&&a[x].right)

{

ans+=min(a[x].v-a[a[x].left].v,a[a[x].right].v-a[x].v);

a[a[x].left].right=a[x].right;

a[a[x].right].left=a[x].left;

}

else if(!a[x].left)

{

ans+=a[a[x].right].v-a[x].v;

a[a[x].right].left=0;

}

else

{

ans+=a[x].v-a[a[x].left].v;

a[a[x].left].right=0;

}

printf("%d",ans);

return 0;

}

splay

#include<iostream>
#include<cstdio>
#define inf 1000000000
using namespace std;
int ans,n,t1,t2,rt,size;
int tr[50001][2],fa[50001],num[50001];
void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y],l,r;
    if(tr[y][0]==x)l=0;else l=1;r=l^1;
    if(y==k)k=x;
    else{if(tr[z][0]==y)tr[z][0]=x;else tr[z][1]=x;}
    fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
    tr[y][l]=tr[x][r];tr[x][r]=y;
 }
void splay(int x,int &k)
{
	int y,z;
	while(x!=k)
	{
		y=fa[x],z=fa[y];
		if(y!=k)
		{
			if((tr[y][0]==x)^(tr[z][0]==y))rotate(x,k);
			else rotate(y,k);
		}
		rotate(x,k);
	}
}
void ins(int &k,int x,int last)
{
     if(k==0){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;}
     if(x<num[k])ins(tr[k][0],x,k);
	 else ins(tr[k][1],x,k);
 }
void ask_before(int k,int x)
{
     if(k==0)return;
     if(num[k]<=x){t1=num[k];ask_before(tr[k][1],x);}
     else ask_before(tr[k][0],x);
 }
void ask_after(int k,int x)
{
   if(k==0)return;
   if(num[k]>=x){t2=num[k];ask_after(tr[k][0],x);}
   else ask_after(tr[k][1],x);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
        int x;if(scanf("%d",&x)==EOF)x=0;
        t1=-inf;t2=inf;
	    ask_before(rt,x);
	    ask_after(rt,x);
	    if(i!=1)ans+=min(x-t1,t2-x);
	    else ans+=x;
	    ins(rt,x,0);
	}
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#define inf 1000000000

using namespace std;

int ans,n,t1,t2,rt,size;

int tr[50001][2],fa[50001],num[50001];

void rotate(int x,int &k)

{

int y=fa[x],z=fa[y],l,r;

if(tr[y][0]==x)l=0;else l=1;r=l^1;

if(y==k)k=x;

else{if(tr[z][0]==y)tr[z][0]=x;else tr[z][1]=x;}

fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;

tr[y][l]=tr[x][r];tr[x][r]=y;

}

void splay(int x,int &k)

{

int y,z;

while(x!=k)

{

y=fa[x],z=fa[y];

if(y!=k)

{

if((tr[y][0]==x)^(tr[z][0]==y))rotate(x,k);

else rotate(y,k);

}

rotate(x,k);

}

void ins(int &k,int x,int last)

{

if(k==0){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;}

if(x<num[k])ins(tr[k][0],x,k);

else ins(tr[k][1],x,k);

}

void ask_before(int k,int x)

{

if(k==0)return;

if(num[k]<=x){t1=num[k];ask_before(tr[k][1],x);}

else ask_before(tr[k][0],x);

}

void ask_after(int k,int x)

{

if(k==0)return;

if(num[k]>=x){t2=num[k];ask_after(tr[k][0],x);}

else ask_after(tr[k][1],x);

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

int x;if(scanf("%d",&x)==EOF)x=0;

t1=-inf;t2=inf;

ask_before(rt,x);

ask_after(rt,x);

if(i!=1)ans+=min(x-t1,t2-x);

else ans+=x;

ins(rt,x,0);

}

printf("%d",ans);

return 0;

}

平衡树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#define inf 1000000000
using namespace std;
int t1,t2,n,sz,rt,ans;
int l[50001],r[50001],v[50001],rnd[50001],s[50001];
void update(int k){s[k]=s[l[k]]+s[r[k]]+1;}
void rturn(int &k)
{int t=l[k];l[k]=r[t];r[t]=k;s[t]=s[k];update(k);k=t;}
void lturn(int &k)
{int t=r[k];r[k]=l[t];l[t]=k;s[t]=s[k];update(k);k=t;}
void insert(int &k,int x)
{
	if(!k){k=++sz;v[k]=x;s[k]=1;rnd[k]=rand();return;}
	s[k]++;
	if(x<v[k]){insert(l[k],x);if(rnd[l[k]]<rnd[k])rturn(k);}
	else {insert(r[k],x);if(rnd[r[k]]<rnd[k])lturn(k);}
}
void ask_before(int k,int x)
{
	if(!k)return;
	if(x>=v[k]){t1=v[k];ask_before(r[k],x);}
	else ask_before(l[k],x);
}
void ask_after(int k,int x)
{
	if(!k)return;
	if(x<=v[k]){t2=v[k];ask_after(l[k],x);}
	else ask_after(r[k],x);
}
int main()
{
	//srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;if(scanf("%d",&x)==EOF)x=0;
        t1=-inf;t2=inf;
        ask_before(rt,x);
        ask_after(rt,x);
        if(i!=1)ans+=min(x-t1,t2-x);
        else ans+=x;
        insert(rt,x);
    }
    printf("%d",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<ctime>

#include<cstdlib>

#define inf 1000000000

using namespace std;

int t1,t2,n,sz,rt,ans;

int l[50001],r[50001],v[50001],rnd[50001],s[50001];

void update(int k){s[k]=s[l[k]]+s[r[k]]+1;}

void rturn(int &k)

{int t=l[k];l[k]=r[t];r[t]=k;s[t]=s[k];update(k);k=t;}

void lturn(int &k)

{int t=r[k];r[k]=l[t];l[t]=k;s[t]=s[k];update(k);k=t;}

void insert(int &k,int x)

{

if(!k){k=++sz;v[k]=x;s[k]=1;rnd[k]=rand();return;}

s[k]++;

if(x<v[k]){insert(l[k],x);if(rnd[l[k]]<rnd[k])rturn(k);}

else {insert(r[k],x);if(rnd[r[k]]<rnd[k])lturn(k);}

}

void ask_before(int k,int x)

{

if(!k)return;

if(x>=v[k]){t1=v[k];ask_before(r[k],x);}

else ask_before(l[k],x);

}

void ask_after(int k,int x)

{

if(!k)return;

if(x<=v[k]){t2=v[k];ask_after(l[k],x);}

else ask_after(r[k],x);

}

int main()

{

//srand(time(0));

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

int x;if(scanf("%d",&x)==EOF)x=0;

t1=-inf;t2=inf;

ask_before(rt,x);

ask_after(rt,x);

if(i!=1)ans+=min(x-t1,t2-x);

else ans+=x;

insert(rt,x);

}

printf("%d",ans);

return 0;

}

在bzoj上用srand(time(0))会RE

« 「BZOJ1862 / 1056」GameZ游戏排名系统「BZOJ1691」[Usaco2007 Dec] 挑剔的美食家 »

Wuvin

学长你的splay版在codevs上被卡T了。
数据：32767
1
999999
999999
999999
999999
999999
999999
999999
999999
……

Agreement

常数优化
主要是void ask_before(int k,int x)和void ask_after(int k,int x)慢了

我比邻

做好营业额统计还真是不简单。。。

hzwer.com _ Home | http://hzwer.com

「BZOJ1588」[HNOI2002] 营业额统计

Description

Input

Output

Sample Input

Sample Output

HINT

代码

分类目录

热门文章

Myfriends

近期评论