NOIP2012Day1T3-开车旅行

NOIP2012Day1T3-开车旅行题解:首先我们可以分别建立小AAA和小BBB路程森林。其实森林也不用用边表去存储它,只要记录一下fa[i]fa[i]fa[i],即iii点的下一个点就可以了小AAA和小BBB旅行就等价于在这些森林里跑,很容易想到树上倍增。我们可以令f[i][j]f[i][j]f[i][j]为当前AAA开车在第iii个点经过2j2j2^j天后到达的点g1[i][j]g1[i][j]g1[i][j…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

NOIP2012Day1T3-开车旅行
题解:
首先我们可以分别建立小 A A 和小
B


B

路程森林。其实森林也不用用边表去存储它,只要记录一下 fa[i] f a [ i ] ,即 i i 点的下一个点就可以了

A


A

和小 B B 旅行就等价于在这些森林里跑,很容易想到树上倍增。
我们可以令
f[i][j]


f


[


i


]


[


j


]

为当前 A A 开车在第
i


i

个点经过 2j 2 j 天后到达的点
g1[i][j] g 1 [ i ] [ j ] 为当前 A A 开车在第
i


i

个点经过 2j 2 j 天后 A A 走的距离

g2[i][j]


g


2


[


i


]


[


j


]

为当前 A A 开车在第
i


i

个点经过 2j 2 j 天后 B B 走的距离
为什么不需要记录当前
B


B

开车的状态?
j>=1 j >= 1 2j 2 j 后,还是 A A 开车,所以不需要记录
B


B

的状态
有了这三个数组,这道题就迎刃而解了。只要结尾状态和一些细节注意一下即可
Code C o d e :

#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define inf 0x7fffffff
using namespace std;
struct node
{
    int d;ll v;
}p[N];
struct note
{
    int mx,mi;
}t[N*5];
bool cmp(node x,node y)
{
    return x.v<y.v||x.v==y.v&&x.d<y.d;
}
double sum,ans;
int n,m,tot,x,y,k,h[N],a[N],b[N],w[N],g[N][18];
ll f[N][18][2],ana,anb,v[N];
void change(int v,int l,int r,int x)
{
    if(l==r){t[v].mx=t[v].mi=l;return;}
    int m=(l+r)/2;
    if(x<=m)change(v*2,l,m,x);else 
        change(v*2+1,m+1,r,x);
    t[v].mx=max(t[v*2].mx,t[v*2+1].mx);
    t[v].mi=min(t[v*2].mi,t[v*2+1].mi);
}
int getmx(int v,int l,int r,int x,int y)
{
    if(x>y)return 0;
    if(l==x&&r==y)return t[v].mx;
    int m=(l+r)/2;
    if(y<=m)return getmx(v*2,l,m,x,y);else
        if(x>m)return getmx(v*2+1,m+1,r,x,y);else
            return max(getmx(v*2,l,m,x,m),getmx(v*2+1,m+1,r,m+1,y));
}
int getmi(int v,int l,int r,int x,int y)
{
    if(x>y)return n+1;
    if(l==x&&r==y)return t[v].mi;
    int m=(l+r)/2;
    if(y<=m)return getmi(v*2,l,m,x,y);else
        if(x>m)return getmi(v*2+1,m+1,r,x,y);else
            return min(getmi(v*2,l,m,x,m),getmi(v*2+1,m+1,r,m+1,y));
}
void solve(int x,int y)
{
    ana=anb=0;
    for(int j=17;j>=0;j--) 
        if(f[x][j][0]+f[x][j][1]<=y)
        {
            y-=f[x][j][0]+f[x][j][1];
            ana+=f[x][j][0];anb+=f[x][j][1];
            x=g[x][j];
        }
    if(f[x][0][0]<=y)ana+=f[x][0][0];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&v[i]),p[i].v=v[i],p[i].d=i;
    sort(p+1,p+n+1,cmp);
    v[0]=inf;
    for(int i=1;i<=n;i++)
        h[p[i].d]=++tot,w[tot]=p[i].d;
    for(int i=1;i<=n*5;i++)t[i].mi=n+1;
    for(int i=n;i>=1;i--)
    {
        p[1].d=getmi(1,1,n,h[i]+1,n);p[2].d=getmx(1,1,n,1,h[i]-1);
        p[3].d=getmi(1,1,n,p[1].d+1,n);p[4].d=getmx(1,1,n,1,p[2].d-1);
        for(int j=1;j<=4;j++)p[j].v=abs(v[i]-v[w[p[j].d]]);    
        sort(p+1,p+5,cmp);
        if(p[1].d!=0&&p[1].d!=n+1)b[i]=w[p[1].d];
        if(p[2].d!=0&&p[2].d!=n+1)a[i]=w[p[2].d];
        change(1,1,n,h[i]);  
    }
    for(int i=1;i<=n;i++)
    {
        g[i][0]=b[a[i]];
        f[i][0][0]=abs(v[i]-v[a[i]]);
        f[i][0][1]=abs(v[a[i]]-v[b[a[i]]]);
    }
    for(int j=1;j<=17;j++)
        for(int i=1;i<=n;i++)
        {
            g[i][j]=g[g[i][j-1]][j-1];
            f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
            f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];
        }
    scanf("%d",&x);ans=inf;
    for(int i=1;i<=n;i++)
    {
        solve(i,x);
        if(!anb)sum=inf;
            else sum=ana*1.0/anb;
        if(sum<ans||sum==ans&&v[i]>v[k])
            ans=sum,k=i;
    }
    printf("%d\n",k);
    for(scanf("%d",&m);m;m--)
    {
        scanf("%d%d",&x,&y);
        solve(x,y);
        printf("%lld %lld\n",ana,anb);  
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172077.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号