【面试题】网易互娱(游戏)2020校招在线笔试-游戏研发第一批[水平线]

zz/2024/7/17 22:08:14

伞屉国是一个以太阳能为主要发电手段的国家,因此他们国家中有着非常多的太阳能基站,链接着的基站会组合成一个发电集群。但是不幸的是伞屉国不时会遭遇滔天的洪水,当洪水淹没基站时,基站只能停止发电,同时被迫断开与相邻基站的链接。你作为伞屉国的洪水观察员,有着这样的任务:在洪水到来时,计算出发电集群被洪水淹没后被拆分成了多少个集群。

由于远古的宇宙战争的原因,伞屉文明是一个二维世界里的文明,所以你可以这样理解发电基站的位置与他们的链接关系:给你一个一维数组a,长度为n,表示了n个基站的位置高度信息。数组的第i个元素a[i]表示第i个基站的海拔高度是a[i],而下标相邻的基站才相邻并且建立链接,即x号基站与x-1号基站、x+1号基站相邻。特别的,1号基站仅与2号相邻,而n号基站仅与n-1号基站相邻。当一场海拔高度为y的洪水到来时,海拔高度小于等于y的基站都会被认为需要停止发电,同时断开与相邻基站的链接。


输入描述:

每个输入数据包含一个测试点。第一行为一个正整数n,表示发电基站的个数 (0 < n <= 200000)接下来一行有n个空格隔开的数字,表示n个基站的海拔高度,第i个数字a[i]即为第i个基站的海拔高度,对于任意的i(1<=i<=n),有(0 <= a[i] < 2^31-1)接下来一行有一个正整数q(0 < q <= 200000),表示接下来有q场洪水接下来一行有q个整数,第j个整数y[j]表示第j场洪水的海拔为y[j],对于任意的j(1<=j<=n),有(-2^31 < y[j] < 2^31-1)

输出描述:

输出q行,每行一个整数,第j行的整数ans表示在第j场洪水中,发电基站会被分割成ans个集群。标准答案保证最后一个整数后也有换行。

输入例子1:

10
6 12 20 14 15 15 7 19 18 13 
6
15 23 19 1 17 24

输出例子1:

2
0
1
1
2
0

题意不复杂,稍微记以下就能理解,根据题意:

当洪水高度为15时,发电站【6 12 20 14 15 15 7 19 18 13 】将会变成【0 0 5 0 0 0 0 4 3 0 】 此时只剩下2个集群

当洪水高度为23时,发电站【6 12 20 14 15 15 7 19 18 13 】将会变成【0 0 0 0 0 0 0 0 0 0 】 此时只剩下0个集群

就此来看题目还是比较简单的,先贴上博主思路:

m = int(input())
ji_zhan = list(map(int, input().split()))
n = int(input())
hong_shui = list(map(int, input().split()))
for i in hong_shui:                  s = 0                             #s用于记录基站是否相连res = 0                           #res用于记录集群数量for j in ji_zhan:if j > i and s == 0:          #当洪水低于基站时,且前一个基站已淹没s += 1                    #当前基站成为一个集群elif s != 0 and j<= i:        #当洪水高于基站时,且前一个基站没有被淹没s = 0                 #淹没当前基站,将集群保存至res中res += 1if s >0:                          #若遍历完成,仍然存在一个集群(即最后一个基站没被淹没)res += 1                      #集群 + 1print(res)

看上去逻辑上没什么问题,但是跑了一下,发现只跑过了20%的样例就超时了

按我的思路来,时间复杂度为O(n**2),想了很久没想出优化方法,交卷以后看了官方解QAQ

官方解:

enb = int(input())
a_alti = list(map(int, input().split()))
hx_t = int(input())
hx_h = list(map(int, input().split()))rsp_a = list(range(0, enb + 2))   
rsp_a[0] = -1                        
rsp_a[enb + 1] = -1                  # 有效数据在[1:发电站个数]#(此表为已被淹没的基站表,定义两个-1是为了方便后续对是否产生新集群做判断)hx_new_index = [index for index, value in sorted(enumerate(hx_h), key=lambda h: h[1])]#首先用enumerate函数把记录洪水的列表变成一个索引序列,序列中的每个元素是一个包含两个数据的元组,数据一为列表中元素的下标,数据二为列表中元素的值#再对该列表进行排序,排序规则为列表中元组的第二个数据#此时列表为如果洪水为[1,3,5,2,4],则此时列表为[0,3,1,4,2]a_new_index = [index for index, value in sorted(enumerate(a_alti), key=lambda h:h[1])]cluster_num = [0] * hx_t   #创建一个长度为hx_t的列表,列表中每个值都是0,用来保存输出数据k = 0        #k用来遍历基站for i in range(hx_t):               #i 用来遍历洪水new_cluster = 0                 #集群变化量while k+1 <= enb and a_alti[a_new_index[k]] <= hx_h[hx_new_index[i]]:#如果基站尚未遍历完成,且基站的第k小个元素<=洪水中第i+1个元素,则循环继续#如果洪水小于基站,则该洪水可直接跳过循环if rsp_a[(a_new_index[k]+1)-1] == -1 and rsp_a[(a_new_index[k]+1)+1] == -1:  #如果左边被淹了而且右边也被淹了new_cluster -=1         #集群-1elif rsp_a[(a_new_index[k]+1) -1] != -1 and rsp_a[(a_new_index[k]+1)+1] != -1: #如果左右都没被淹new_cluster +=1      #集群+1rsp_a[a_new_index[k]+1] = -1   #基站淹没,变为-1k += 1if i == 0:cluster_num[hx_new_index[i]] = 1 + new_cluster     #初始状态所有基站共同为一个集群,故为1else:cluster_num[hx_new_index[i]] = cluster_num[hx_new_index[i - 1]] + new_cluster        #上一个洪水中剩余的集群 + 这次洪水的变化for cn in cluster_num:print(cn)

此代码参考自 牛客网 用户“牛客680312541号” 

(源码写得比较复杂,而且没有注释,所以改进了一下并加了一些注释方便阅读,总体思路还是很好懂的,不过还是代码还是显得很臃肿,希望大家能提出更好更python的解法)

难度:中等


http://www.ngui.cc/zz/2700277.html

相关文章

【面试题】网易互娱(游戏)2021校园招聘在线笔试 - 服务端开发工程师[文件系统]

昨晚做网易互娱的笔试&#xff0c;比较尴尬的是只能用C/C/Java&#xff0c;而本人对C/C的了解仅限于大一的课程设计&#xff08;而且一年多没用过C写代码了&#xff09;&#xff0c;Java差不多看得懂代码但是没有系统的学过。无奈最后只能用python写了两道题&#xff0c;再用C照…

Python中构造方法和初始化方法

原文链接&#xff1a;https://blog.csdn.net/qq_19707521/article/details/79359858 类的实例化 在python中创建一个新式类时&#xff0c;一般都会定义一个 __init__ 方法&#xff0c;用来对类的实例进行初始化。但是 __init__ 方法并不是类的构造方法&#xff0c;类中真正的构…

LocustIO官方文档

写在前面 最近打算学习LocustIO&#xff0c;但是介于英文水平一般&#xff0c;英文文档读起来还是不太顺畅&#xff0c;于是花了两天时间把整个英文文档翻译了一遍&#xff0c;以供学习之用。翻译过程尽量终于原文&#xff0c;但是由于水平有限&#xff0c;难免会有错失遗漏&a…

统一图片尺寸方法

转自&#xff1a;http://www.cnblogs.com/tornadomeet/archive/2012/03/27/2420088.html // change_img_size.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h"//这句头文件一定要放在最上面&#xff0c;否则很容易报错#include "opencv2/imgproc/im…

quartz(六)定时任务的暂停、关闭等操作说明

定时任务的暂停、关闭等操作说明 基于quartz3.0版本总结一些quartz定时任务的暂停、恢复、删除等操作。 定时任务的删除等操作主要是基于JobKey或TriggerKey。 暂停Job: //通过JobName以及JobGroup获得JobKeyJobKey jobKey JobKey.jobKey("aaaa" 1, JOB_GROUP_N…

Redis总结(八)redis单线程还是多线程问题

redis为什么可以支持高并发和它内部的工作模式有不可分割的关系&#xff1a; 绝大部分请求是纯粹的内存操作&#xff08;非常快速&#xff09;采用单线程,避免了不必要的上下文切换和竞争条件非阻塞IO - IO多路复用 Redis客户端对服务端的每次调用都经历了发送命令&#xff0…

Struts2详述

提到Struts就不得不提到MVC&#xff0c;因为struts2就是基于MVC设计理念而开发的Java Web应用框架&#xff0c;下面先介绍一下MVC的原理&#xff1a;MVC全名是Model View Controller&#xff0c;是模型(model)&#xff0d;视图(view)&#xff0d;控制器(controller)的缩写&…

git和maven

很多人应该用过svn cvs之类的代码版本管理工具&#xff0c;git也是其中之一。 svn和git最大的几个区别要点&#xff0c;svn必须要有服务端&#xff0c;网络能连上服务端才能提交和更新&#xff0c;git不需要&#xff0c;每一台装了git的电脑都是服务端&#xff0c;各台电脑之间…

Java中常用的排序算法

分类&#xff1a; 1&#xff09;插入排序&#xff08;直接插入排序、希尔排序&#xff09; 2&#xff09;交换排序&#xff08;冒泡排序、快速排序&#xff09; 3&#xff09;选择排序&#xff08;直接选择排序、堆排序&#xff09; 4&#xff09;归并排序 5&#xff09;分配排…

java中的设计模式总

设计模式&#xff08;Design pattern&#xff09;是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 毫无疑问&#xff0c;设计模式于己于他人于系统都是多赢的&#xff0c;设计模…