「BZOJ1367」[Baltic2004] sequence

2014年12月17日5,0514

Description

Input

Output

一个整数R

Sample Input

7
9
4
8
20
14
15
18

Sample Output

HINT

所求的Z序列为6,7,8,13,14,15,18.
R=13

题解

hyh论文例题

http://wenku.baidu.com/link?url=t55yGX-UkUdEXBhpvBwuzjKP16F7lFl0RKSVVBBW5zXWRB7rRXvLLj1jM-pzhbH834hQl0KKT4va247VmSepsGDSrYF1E3le_WpnKc2xfCi

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#define N 1000005
#define inf 1000000000
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n,now;
int a[N],root[N];
int L[N],R[N],tot[N];
struct Ltree{
	int cnt;
	int l[N],r[N];
	int v[N],Size[N],d[N];
	int merge(int x,int y){
		if(x==0||y==0)return x+y;
		if(v[x]<v[y])swap(x,y);
		r[x]=merge(r[x],y);
		Size[x]=Size[l[x]]+Size[r[x]]+1;
		if(d[r[x]]>d[l[x]])swap(l[x],r[x]);
		d[x]=d[r[x]]+1;
		return x;
	}
	inline int top(int x){
		return v[x];
	}
	inline int size(int x){
		return Size[x];
	}
	inline void pop(int &x){
		x=merge(l[x],r[x]);
	}
	inline int new_heap(int x){
		v[++cnt]=x;
		Size[cnt]=1;
		l[cnt]=r[cnt]=d[cnt]=0;
		return cnt;
	}
}heap;
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read()-i;
	for(int i=1;i<=n;i++)
	{
		now++;
		root[now]=heap.new_heap(a[i]);
		tot[now]=1;
		L[now]=R[now]=i;
		while(now>1&&heap.top(root[now-1])>heap.top(root[now]))
		{
			now--;
			root[now]=heap.merge(root[now],root[now+1]);
			tot[now]+=tot[now+1];R[now]=R[now+1];
			while(heap.size(root[now])*2>tot[now]+1)
			    heap.pop(root[now]);
		}
	}
	for(int i=1;i<=now;i++)
		for(int j=L[i],t=heap.top(root[i]);j<=R[i];j++)
			ans+=abs(a[j]-t);
	printf("%lld",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#define N 1000005

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans;

int n,now;

int a[N],root[N];

int L[N],R[N],tot[N];

struct Ltree{

int cnt;

int l[N],r[N];

int v[N],Size[N],d[N];

int merge(int x,int y){

if(x==0||y==0)return x+y;

if(v[x]<v[y])swap(x,y);

r[x]=merge(r[x],y);

Size[x]=Size[l[x]]+Size[r[x]]+1;

if(d[r[x]]>d[l[x]])swap(l[x],r[x]);

d[x]=d[r[x]]+1;

return x;

}

inline int top(int x){

return v[x];

}

inline int size(int x){

return Size[x];

}

inline void pop(int &x){

x=merge(l[x],r[x]);

}

inline int new_heap(int x){

v[++cnt]=x;

Size[cnt]=1;

l[cnt]=r[cnt]=d[cnt]=0;

return cnt;

}

}heap;

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read()-i;

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

{

now++;

root[now]=heap.new_heap(a[i]);

tot[now]=1;

L[now]=R[now]=i;

while(now>1&&heap.top(root[now-1])>heap.top(root[now]))

{

now--;

root[now]=heap.merge(root[now],root[now+1]);

tot[now]+=tot[now+1];R[now]=R[now+1];

while(heap.size(root[now])*2>tot[now]+1)

heap.pop(root[now]);

}

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

for(int j=L[i],t=heap.top(root[i]);j<=R[i];j++)

ans+=abs(a[j]-t);

printf("%lld",ans);

return 0;

}

« 「BZOJ1455」罗马游戏「BZOJ2809」[Apio2012] dispatching »

conan_c

题目到底是不下降序列呢。。还是递增序列呢。。

zlxFTH

把ai减i就可以把递增序列变成不下降序列

cyx

程序好像有bug
数据为5 5 4 3 2 1 输出20 正解应为12 （1 2 3 4 5）
不解

hzwer

代码贴错了。此题应该维护大根堆TAT

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

「BZOJ1367」[Baltic2004] sequence

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论