1. 全栈程序员必看首页

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

全栈程序员-站长 • • 未分类 • 阅读 5

开车旅行游戏_开车周游世界题目链接这道题最基本的思路是用倍增，但是其实它的难点在预处理部分。倍增的部分此次就不细说了，和之前的最近公共祖先的思想类似。我们主要来探讨一下预处理的部分。我们需要预处理出每个城市小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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/172075.html原文链接：https://javaforall.net

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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