怎么提高开车技术_全日行车计划

怎么提高开车技术_全日行车计划Description现在有n个城市,每个城市有它的高度HiH_i,保证每个HiH_i互不相同。我们定义两个城市之间的距离disi,j=|Hi−Hj|dis_{i,j}=|H_i-H_j|,并且只能从编号小的城市去到编号大的城市。现在有两个人,小A和小B要开车(雾)去旅行。小A先开一天,小B再开一天。每一天都可以从一个开到另一个城市。小A会选择去离当前城市第二近的城市,小B会选择去离当前城市最近的那

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

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

Description

现在有n个城市,每个城市有它的高度 Hi ,保证每个 Hi 互不相同。我们定义两个城市之间的距离 disi,j=|HiHj| ,并且只能从编号小的城市去到编号大的城市。现在有两个人,小A和小B要开车(雾)去旅行。小A先开一天,小B再开一天。每一天都可以从一个开到另一个城市。小A会选择去离当前城市第二近的城市,小B会选择去离当前城市最近的那个城市。如果他们行驶的总路程将会超过给定的X就会不继续开车(∩_∩),结束旅行。求:
1:给定一个X,求从哪一个城市出发,小A行驶的路程/小B行驶的路程最小。(认为一个数/0=∞)。若有多个城市相等,选择高度最高的那个。
2:给出m个询问,每次询问从S出发,限制为X,小A走的路程和小B走的路程。

Solution

观察题目,一个很明显的想法就是把小A和小B从每个点出发将要去到的城市预处理出来。这一个东西可以用双向链表啦~线段树啦~平衡树啦~并查集啦~ set啦 ……等等这些很神奇的东西。(我打线段树预处理打了60行(TAT),Howar Li表示并查集大法好,不超过30行(QAQ))。
然后,你就可以打倍增了。嗯。就是这么简单。
设f[i][j][0]表示从城市i出发,小A经过2^j轮(注意是轮)之后走的路程。
f[i][j][1]表示小B走的路程
g[i][j]表示走到那个城市。
转移很明显(只要你会打RMQ),嗯。
然后对于第一个询问,暴力枚举起点即可。
对于第二个询问,直接倍增即可。
是不是很简单!?

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define db double
#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;
}
db sum,ans;
int n,m,tot,x,y,k;
int 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;
    fd(j,17,0) 
        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);
    fo(i,1,n) scanf("%lld",&v[i]),p[i].v=v[i],p[i].d=i;
    sort(p+1,p+n+1,cmp);v[0]=inf;
    fo(i,1,n) h[p[i].d]=++tot,w[tot]=p[i].d;
    fo(i,1,n*5) t[i].mi=n+1;
    fd(i,n,1) {
        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);
        fo(j,1,4) 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]);         
    }
    fo(i,1,n) {
        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]]]);
    }
    fo(j,1,17)
        fo(i,1,n) {
            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;
    fo(i,1,n) {
        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/172066.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • nessus安装使用教程_ps激活成功教程版安装教程

    nessus安装使用教程_ps激活成功教程版安装教程Nessus在Windows版本和Linux版本环境下安装

  • java.net.DatagramSocket

    java.net.DatagramSocket此类表示用于发送和接收数据报包的套接字。数据报套接字是分组传送服务的发送或接收点。在数据报套接字上发送或接收的每个数据包都是单独寻址和路由的。从一台机器发送到另一台机器的多个分组可以被不同地路由,并且可以以任何顺序到达。在可能的情况下,新构造DatagramSocket的SO_BROADCAST插座选项已启用,以便允许广播数据报的传输。为了接收广播数据包,应将DatagramSocket绑…

  • html怎么动态获取系统时间_代码实现获取当前的地理位置

    html怎么动态获取系统时间_代码实现获取当前的地理位置HTML+JS动态获取当前时间效果图:说明:JavaScript中Date对象创建Date对象的语法:varmyDate=newDate()常用Date对象方法:方法描述Date()返回当日的日期和时间getDate()从Date对象返回一个月中的某一天(1~31)getDay()从Date对象返回一周中的某…

  • 中高级Java开发面试题,最难的几道Java面试题,看看你跪在第几个

    中高级Java开发面试题,最难的几道Java面试题,看看你跪在第几个5.为什么char数组比Java中的String更适合存储密码?另一个基于String的棘手Java问题,相信我只有很少的Java程序员可以正确回答这个问题。这是一个真正艰难的核心Java面试问题,并且需要对String的扎实知识才能回答这个问题。这是最近在Java面试中向我的一位朋友询问的问题。他正在接受技术主管职位的面试,并且有超过6年的经验。如果你还没有遇到过这种情况,那么字符数组和字符串可以用来存储文本数据,但是选择一个而不是另一个很难。但正如我的朋友所说,任何

  • redisson分布式锁实现原理_redisson连接池

    redisson分布式锁实现原理_redisson连接池redissonlock、tryLock分布式锁原理解析

    2022年10月15日
  • 苹果系统自带的计算机怎么恢复出厂设置,苹果Macbook电脑怎么恢复出厂设置【图文】…

    苹果系统自带的计算机怎么恢复出厂设置,苹果Macbook电脑怎么恢复出厂设置【图文】…苹果电脑预装Mac系统,简洁又安全,不过使用时间长了,难免会碰到一些问题,导致系统运行速度变得卡顿。恢复出厂设置是一个不错的办法,之前windows系统恢复出厂设置比较简单,但苹果Macbook电脑怎么恢复出厂设置?Mac系统提供恢复出厂系统的功能,主要分为离线和在线两种方法,感兴趣的一起来学习。苹果Macbook恢复出厂设置删除数据的方法:提醒:恢复出厂设置前请做好数据备份,以免对您造成损失。1…

发表回复

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

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