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

开车旅行游戏_开车周游世界题目链接这道题最基本的思路是用倍增,但是其实它的难点在预处理部分。倍增的部分此次就不细说了,和之前的最近公共祖先的思想类似。我们主要来探讨一下预处理的部分。我们需要预处理出每个城市小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)


相关推荐

  • java中的invoke方法_java中的反射,invoke方法详解

    java中的invoke方法_java中的反射,invoke方法详解展开全部就是调用类中的方法e68a843231313335323631343130323136353331333365646239,最简单的用法是可以把方法参数化,invoke(class,method)比如你Test类里有一系列名字相似的方法setValue1、setValue2等等。可以把方法名存进数组v[],然后循环里invoke(test,v[i]),就顺序调用了全部setValue如:…

  • 企业微信机器人python脚本执行报错-‘errcode‘: 40008, ‘errmsg‘: ‘Warning: wrong json format. invalid message type

    企业微信机器人python脚本执行报错-‘errcode‘: 40008, ‘errmsg‘: ‘Warning: wrong json format. invalid message type错误内容{‘errcode’:40008,‘errmsg’:‘Warning:wrongjsonformat.invalidmessagetype,hint:[1596176563_47_d9bbe040d5a640ea75f8625e35783c76],fromip:61.183.117.38,moreinfoathttps://open.work.weixin.qq.com/devtool/query?e=40008’}查看官网错误代码意义40008 不合法

  • 远程调试部署在容器中的springboot项目「建议收藏」

    远程调试部署在容器中的springboot项目「建议收藏」问题:访问网站,会根据ip判断访客所处位置,但部分ip插入数据库失败。 以为是一次小问题,很快就解决了,没想到最终花了6个小时左右,才搞清楚。分析 :1、将本地程序跑起来,发现一切正常,可以插入到数据库。但问题在线上确实妥妥的出现的,而我现在日志级别是info,没有错误日志。所有准备Debug线上程序,之前只debug过使用基本的tomcat发布。而我现在的jar是使用docker构建的镜像,运行的镜像。 2、问题从线上转化到了,我需要远程debug线上程序发现问题,并将之解决。查各种资料,配置

  • 【2022年更新】手把手教你去除 WinRAR 的弹窗广告

    【2022年更新】手把手教你去除 WinRAR 的弹窗广告WinRAR作为知名的老牌压缩软件,二十余年来始终风靡全球,经久不衰。但对于中国用户,其简体中文的个人免费版安装后会有“评估版本”的标记,而且每次启动时会有代理商的弹窗广告。本文教你如何去除标记和弹窗广告,让你的WinRAR恢复纯净体验。

  • linux安装node js的二进制文件安装方式的注意事项

    linux安装node js的二进制文件安装方式的注意事项

  • 启用shift后门的方法_服务器可以拿来干什么

    启用shift后门的方法_服务器可以拿来干什么提权工具如下:cmd.exeChurrasco.exenc.exe提权前提:Wscript组件成功开启如果Wscript组件被关闭,则使用以下方法开启:源代码:&lt;objectrunat=serverid=oScriptlhnscope=pageclassid="clsid:72C24DD5-D70A-438B-8A42-98424B88AFB8"&gt;&lt;/…

发表回复

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

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