开车旅行游戏_开车周游世界

开车旅行游戏_开车周游世界题目链接这道题最基本的思路是用倍增,但是其实它的难点在预处理部分。倍增的部分此次就不细说了,和之前的最近公共祖先的思想类似。我们主要来探讨一下预处理的部分。我们需要预处理出每个城市小A和小B的选择目标和对应的距离,接下来就可以处理出进行2k轮开车的目的地和距离了。所以前者才是重中之重,而前者如果要用暴力的方法会tle的。有人可能会疑惑,我们找当前点的后面两三个不就可以了?为什么会tle呢?实际上并不是序号相差很远距离就很远,实际上有可能第一个城市和最后一个城市最近,可以举个例子,城市海拔如下:

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

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

题目链接
这道题最基本的思路是用倍增,但是其实它的难点在预处理部分。
倍增的部分此次就不细说了,和之前的最近公共祖先的思想类似。
我们主要来探讨一下预处理的部分。
我们需要预处理出每个城市小A和小B的选择目标和对应的距离,接下来就可以处理出进行2k轮开车的目的地和距离了。所以前者才是重中之重,而前者如果要用暴力的方法会tle的。
有人可能会疑惑,我们找当前点的后面两三个不就可以了?为什么会tle呢?
实际上并不是序号相差很远距离就很远,实际上有可能第一个城市和最后一个城市最近,可以举个例子,城市海拔如下:
1 3 4 5 6 7 8 9 10 11 2
也许你也会有疑问,不是说右边的城市在左边城市的东边吗?这可能吗?
注意这题并不是线性的,而是2D的。所以可以画出如下的图:
在这里插入图片描述

所以,这么看来,暴力算法的复杂度就是n方,就会超时。
所以我们需要换种方法。
我们不妨换种顺序,因为是用海拔来决定高度,所以海拔相距最近的,一定是距离最近的。
所以我们可以按照海拔进行排序,排好序后就按照这个顺序建立双向链表。
这时我们就知道了,对于某一城市,小a和小b要么没有选择,要么选择的城市一定在当前城市链表中的前两个和两个中。
为什么不是前一个和后一个?因为如果一个点在链表边上,它就只有一侧,所以把特殊情况考虑在内,就是前两个和后两个。
那么你可能又会觉得奇怪,万一这几个当中有城市在当前城市的西边怎么办?这样这个范围就可能不够了?
所以我们的处理顺序就成了很大的很关键,我们按照城市编号顺序去处理每个城市的目标,处理完后就把当前城市删除(这也是用双向链表的原因),这样每次处理就可以保证当前链表中的其他城市均在当前城市的东边,而保证我们所取的范围是够的。
当然你也许还会有疑问,那我怎么定位要处理的城市在链表中的位置呢?
这个准备的指针数组就好了。
这样就可以把预处理的复杂度从O(n2)降低到O(n),这样就可以过了
下面是参考代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAX 2000000000
using namespace std;
const int maxn=100005;
struct City{ 

int num;
int h;
City *last,*next; 
}city[maxn]; 
City *pos[maxn];
long long n,m,x0,ss[maxn],xx[maxn],h[maxn],maxk; 
long long aaim[maxn],baim[maxn],adis[maxn],bdis[maxn];
long long longdis[maxn][20],longaim[maxn][20];
long long alongdis[maxn][20],alongaim[maxn][20];
long long s0,da=-1,db=-1;
void fun1(long long curs){ 

long long tot=0,cura=0,curb=0,curn=curs;
for(int k=maxk;k>=0;k--){ 

if(longaim[curn][k]!=0&&longdis[curn][k]+tot>x0){ 

continue;
}
if(longaim[curn][k]==0){ 

continue;
}
tot+=longdis[curn][k];
cura+=alongdis[curn][k];
curn=longaim[curn][k];
}
curb=tot-cura;
if(aaim[curn]!=0&&tot+adis[curn]<=x0){ 

tot+=adis[curn];
cura+=adis[curn];
}
if(da==-1){ 

s0=curs;
da=cura;
db=curb;
}else if(db==0&&curb==0&&h[curs]>h[s0]){ 

s0=curs;
da=cura;
db=curb;
}else if(db==0){ 

s0=curs;
da=cura;
db=curb;
}else if(curb==0){ 

}else if(da*curb>db*cura){ 

s0=curs;
da=cura;
db=curb;
}else if(da*curb==db*cura&&h[curs]>h[s0]){ 

s0=curs;
da=cura;
db=curb;
} 
}
void fun2(long long s,long long xi){ 

long long tot=0,cura=0,curb=0,curn=s;
for(int k=maxk;k>=0;k--){ 

if(longaim[curn][k]!=0&&longdis[curn][k]+tot>xi){ 

continue;
}
if(longaim[curn][k]==0){ 

continue;
}
tot+=longdis[curn][k];
cura+=alongdis[curn][k];
curn=longaim[curn][k];
}
curb=tot-cura;
if(aaim[curn]!=0&&tot+adis[curn]<=xi){ 

tot+=adis[curn];
cura+=adis[curn];
}
printf("%d %d\n",cura,curb); 
}
int cmp(City a,City b){ 

return a.h<b.h;
}
void update(City cur,City aim){ 

if((abs(cur.h-aim.h)<bdis[cur.num])||(abs(cur.h-aim.h)==bdis[cur.num]&&aim.h<pos[baim[cur.num]]->h)){ 

adis[cur.num]=bdis[cur.num];
aaim[cur.num]=baim[cur.num];
bdis[cur.num]=abs(cur.h-aim.h);
baim[cur.num]=aim.num;
}else if((abs(cur.h-aim.h)<adis[cur.num])||(abs(cur.h-aim.h)==adis[cur.num]&&aim.h<pos[aaim[cur.num]]->h)){ 

adis[cur.num]=abs(cur.h-aim.h);
aaim[cur.num]=aim.num;
}
}
int main(){ 

scanf("%lld",&n);
for(int i=1;i<=n;i++){ 

scanf("%lld",&city[i].h);
adis[i]=bdis[i]=MAX;
city[i].num=i;
}
scanf("%lld%lld",&x0,&m);
for(int i=0;i<m;i++){ 

scanf("%lld%lld",&ss[i],&xx[i]);
}
sort(city+1,city+n+1,cmp);
for(int i=1;i<=n;i++){ 

if(i==1){ 

city[i].last=NULL;
}else{ 

city[i].last=&city[i-1];
}
if(i==n){ 

city[i].next=NULL;
}else{ 

city[i].next=&city[i+1];
}
pos[city[i].num]=&city[i];
}
for(int i=1;i<=n;i++){ 

City *p;
p=pos[i]->last;
if(p!=NULL){ 

update(*pos[i],*p);
p=p->last;
if(p!=NULL){ 

update(*pos[i],*p);
}
}
p=pos[i]->next;
if(p!=NULL){ 

update(*pos[i],*p);
p=p->next;
if(p!=NULL){ 

update(*pos[i],*p);
}
}
if(pos[i]->next!=NULL){ 

pos[i]->next->last=pos[i]->last;
}
if(pos[i]->last!=NULL){ 

pos[i]->last->next=pos[i]->next;
}
} 
for(int i=1;i<=n;i++){ 

if(aaim[i]!=0&&baim[aaim[i]]!=0){ 

longdis[i][0]=adis[i]+bdis[aaim[i]];
longaim[i][0]=baim[aaim[i]];
alongdis[i][0]=adis[i];
alongaim[i][0]=baim[aaim[i]];
}else{ 

longaim[i][0]=0;
longdis[i][0]=MAX;
alongdis[i][0]=MAX;
alongaim[i][0]=0;
}
}
for(int k=1;(1<<k)<=n;k++){ 

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

if(longaim[i][k-1]!=0&&longaim[longaim[i][k-1]][k-1]!=0){ 

longdis[i][k]=longdis[i][k-1]+longdis[longaim[i][k-1]][k-1];
longaim[i][k]=longaim[longaim[i][k-1]][k-1];
}else{ 

longdis[i][k]=MAX;
longaim[i][k]=0;
}
if(alongaim[i][k-1]!=0&&alongaim[alongaim[i][k-1]][k-1]!=0){ 

alongdis[i][k]=alongdis[i][k-1]+alongdis[alongaim[i][k-1]][k-1];
alongaim[i][k]=alongaim[alongaim[i][k-1]][k-1];
}else{ 

alongdis[i][k]=MAX;
alongaim[i][k]=0;
}
}
maxk=k;
}	
for(int i=1;i<=n;i++){ 

fun1(i);
}
printf("%d\n",s0);
for(int i=0;i<m;i++){ 

fun2(ss[i],xx[i]);
}
return 0;
} 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)
blank

相关推荐

  • zigbee 协议栈睡眠用法[通俗易懂]

    zigbee 协议栈睡眠用法[通俗易懂]大家都知道2430有3种睡眠模式,pm2模式比较省功耗而且可以被定时唤醒;pm3模式最省电但是只能被外部中断唤醒。开启睡眠功能很简单:首先确认/TexasInstruments/ZStack-1.4.3-1.2.1/Projects/zstack/Tools/CC2430DB目录下的f8wConfig.cfg文件中DRFD_RCVC_ALWAYS_ON定义为FALSE;然后在IAR的

  • datagrip激活码2021(JetBrains全家桶)

    (datagrip激活码2021)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html0E14HXZ4QL-eyJsa…

  • 函数的凹凸性_函数凹凸性与图像

    函数的凹凸性_函数凹凸性与图像设函数$f(x)$在区间$I$上有定义,在$I$内任取两点$x_{1},x_{2}$,对任意的 $\lambda\in(0,1)$,有 $\lambdax_{1

  • 数字信号处理课程实验报告(数字信号处理需要什么基础)

    问题重述 DSP课程实验计算机模拟产生多频率信号:编写通用的FFT子程序 设置参数,对信号进行频谱分析 对信号分别以满足和不满足奈奎斯特采样定理的采样率进行采样,观察其频谱变化 设计低通、高通、带通和带阻滤波器,对多频率信号进行滤波处理 撰写实验报告,内容包括实验步骤、流程图、源程序、设置参数、输出结果(图)、结果分析(结合原理)例如:模拟信号:用一个FFT处理…

  • linux -umask

    linux -umask

  • Xlsx结合File-Saver实现前端页面表格导出Excel为文件

    Xlsx结合File-Saver实现前端页面表格导出Excel为文件系列文章目录提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加例如:第一章Python机器学习入门之pandas的使用提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录系列文章目录前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结前言提示:这里可以添加本文要记录的大概内容:例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。提示:以下是本篇文章正文内容,下面案例

发表回复

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

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