首页 > 代码库 > vijos P1459车展

vijos P1459车展

2024-08-15 07:39:33   220人阅读

P1459车展
Accepted
标签：数据结构 平衡树数据结构 堆重游SC theme Park
 
 

描述

遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：
L1 R1
L2 R2
…
Lm Rm
单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。

为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有一个人，所以只好对每个展台依次操作。每次展览结束后，展台高度自动恢复到初始高度。

请告诉管理员为了举办所有展览，他最少需要花多少时间将展台调整好。

格式

输入格式

第一行为两个正整数n、m。

第二行共n个非负整数，表示第i辆车展台的高度h[i]。

接下来m行每行2个整数Li、Ri（Li≤Ri）。

输出格式

一个正整数，调整展台总用时的最小值。

样例1

样例输入1[复制]

 
6 44 1 2 13 0 91 52 63 42 2

样例输出1[复制]

 
48

限制

各个测试点1s

提示

对于50％的数据 n≤500，m≤1000；
对于80％的数据 n≤1000，m≤100000；
对于100％的数据n≤1000，m≤200000；
答案在2^64以内。

附上一组测试数据

输入

10 10 
28 5 10 16 24 14 7 15 20 0 
1 7 
2 4 
9 10 
9 10 
8 9 
3 6 
7 10 
3 9 
4 7 
6 10

输出

222

AC代码1：

消耗时间2762 ms
消耗内存572 KiB
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#define ll long longusing namespace std;const int N=1e3+10;int n,m,a[N],d[N]; ll tot=0;inline const int read(){    register int x=0,f=1;    register char ch=getchar();    while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}inline int abs(int x){    return x>0?x:-x;}int main(){    n=read();m=read();    for(int i=1;i<=n;i++) a[i]=read();    memcpy(d,a,sizeof a);    for(int i=1,l,r,mid;i<=m;i++){        l=read();r=read();mid=l+r>>1;        nth_element(a+l,a+mid,a+r+1);        ll t1=0;        for(int j=l;j<=r;j++) t1+=abs(a[j]-a[mid]);        tot+=t1;        memcpy(a,d,sizeof d);    }    cout<<tot;    return 0;}

 

AC代码2：

消耗时间576 ms
消耗内存1564 KiB
#include<cstdio>#include<algorithm>#define ll long longusing namespace std;const int N=1001<<2;const int M=N*20;int sum[M],ls[M],rs[M];int T[N],num[N],a[N],san[N],tot;inline const int read(){    register int x=0,f=1;    register 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;}void build(int &rt,int l,int r){    rt=++tot;    sum[rt]=0;    if(l==r) return ;    int mid=(l+r>>1);    build(ls[rt],l,mid);    build(rs[rt],mid+1,r);}void updata(int &rt,int last,int p,int l,int r){    rt=++tot;    ls[rt]=ls[last];    rs[rt]=rs[last];    sum[rt]=sum[last]+1;    if(l==r) return ;    int mid=(l+r>>1);    if(p<=mid)        updata(ls[rt],ls[last],p,l,mid);    else        updata(rs[rt],rs[last],p,mid+1,r);}int query(int l,int r,int x,int y,int k){    if(l==r) return l;    int mid=(l+r>>1);    int cnt=sum[ls[y]]-sum[ls[x]];    if(k<=cnt)        return query(l,mid,ls[x],ls[y],k);    else        return query(mid+1,r,rs[x],rs[y],k-cnt);}ll total;int main(){    int n=read(),m=read();    for(int i=1;i<=n;i++) san[i]=num[i]=a[i]=read();    stable_sort(san+1,san+n+1);    int cnt=unique(san+1,san+n+1)-(san+1);    build(T[0],1,cnt);    for(int i=1;i<=n;i++) num[i]=lower_bound(san+1,san+cnt+1,num[i])-san;    for(int i=1;i<=n;i++) updata(T[i],T[i-1],num[i],1,cnt);    for(int i=1;i<=m;i++){        int x=read(),y=read(),k=(y-x>>1)+1;        int id=query(1,cnt,T[x-1],T[y],k);        int smid=san[id];        ll t1=0;        for(int j=x;j<=y;j++) t1+=abs(a[j]-smid);        total+=t1;    }    printf("%lld",total);    return 0;}

 

vijos P1459车展


联系
我们