首页 > 其他分享 >【蔚来汽车】蔚来20220713第三题-旅游规划

【蔚来汽车】蔚来20220713第三题-旅游规划

时间:2024-02-29 16:45:04浏览次数:30  
标签:maxhappy city curhappy 20220713 花费 蔚来 城市 旅游

【蔚来汽车】蔚来20220713第三题-旅游规划

牛牛对 n 个城市旅游情况进行了规划,已知每个城市有两种属性 x 和 y ,其中 x 表示去第 i 号城市的花费,y 表示在第 i 号城市游玩后会得到的开心值。
  现在牛牛希望从中挑选出一些城市去游玩,但挑选出的城市必须满足任意两个城市之间花费差值的绝对值小于 k
  请你帮他计算出在满足上述条件下能得到最大的开心值是多少

输入描述:
第一横输入两个整数 n 和 k
接下来 n 行,每行输入两个整数 x 和 y ,分别表示每个城市的两种属性
1 < n <= 100000
1 < k <= 1000000000
0 < x,y <= 1000000000

输出描述:
输出一个整数表示答案

示例输入:

5 3
1 3
2 1
5 2
3 1
4 3

示例输出:

6

思路

先根据城市的花费进行排序得到城市序列,经过分析可以知道:

  • 要得到最大的开心值,选择旅游的城市必然是连续的一段;(如果不连续,比如选择了排序后的第【2】、【4】、【5】个城市,那么再加上第【3】个城市肯定也满足任意两个城市之间花费差值的绝对值小于 k,并且开心值更大)
  • 对于连续的城市序列,任意两个城市之间花费差值的绝对值小于 k等价于最大和最小的城市花费之间差值的绝对值小于 k

因此求解问题转为找到一段连续序列的开头和结尾,使得城市序列的开心值最大。

题解

import sys

for line in sys.stdin:
    a = line.split()
    n = int(a[0])
    k = int(a[1])
    city = []
    for i in range(n):
        city.append(list(map(int, input().split())))
    city.sort(key=lambda x: x[0])
    maxhappy = 0
    curhappy = 0
    # 滑动窗口法
    for i in range(n):
        curhappy = city[i][1]
        j = i + 1
        while j < n and city[j][0] - city[i][0] < k:
            curhappy += city[j][1]
            j += 1
        maxhappy = max(maxhappy, curhappy)

    print(maxhappy)

标签:maxhappy,city,curhappy,20220713,花费,蔚来,城市,旅游
From: https://www.cnblogs.com/zhangdoudou/p/18044728

相关文章

  • 旅游景点 Tourist Attractions (壮压 DP)题解
    简化题意题目链接——不卡内存班题目链接——卡内存版给定\(n\)个点和\(m\)条边组成的无向图,按照一定限制要求停留\(2\simk+1\)共\(k\)个点(可以经过但不停留),求最短的从\(1\)出发到\(n\)的路径长。限制情况如下:共有\(q\)个限制,接下来\(q\)行,每行两个数\(x......
  • [刷题笔记] P9751 [CSP-J 2023] 旅游巴士
    Problem_LinkDescription给定一个\(n\)个点,\(m\)条边的有向图。起点为\(1\),终点为\(n\)。起始时间和终止时间必须是\(k\)的倍数。通过每条边的时间为\(1\)。每条边有限制\(a_i\)即若通过当前边必须满足当前时间\(t\geqa_i\)。求满足上述限制的前提下,到达终点的最小......
  • 【专题】2023旅游行业洞察报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=33833原文出处:拓端数据部落公众号根据文化和旅游部的数据统计,2023年"五一"假期全国国内共有2.74亿人次进行了旅游,同比增长了70.83%。而端午节假期期间,全国国内出游人数达到1.06亿人次,同比增长了32.3%。消费者对于旅游的热情高涨,文化和旅游行业呈现......
  • Jadoo旅游网的设计与实现代码
     <head> <metacharset="utf-8"> <metahttp-equiv="X-UA-Compatible"content="IE=edge"> <metaname="viewport"content="width=device-width,initial-scale=1"> <!--===========......
  • 36万的售价,蔚来理想卖得,小米卖不得?
    文|AUTO芯球作者|雷歌AreyouOK?雷军被网友们叫“小雷”!被网友一猜再猜的小米SU7的价格,因为一份保险上牌价格单的曝光被网友吵得热热闹闹,曝出的小米汽车顶配上牌保险价格为36.14万。20万以下,人们愿称“雷总”,30万以上价格,人们只愿叫他“小雷”。吃瓜群众就是这么爱憎分明(jianf......
  • 基于SSM的畅玩北海旅游网站的设计与实现
    现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本畅玩北海旅游网站就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完毕庞大的数据信息,使用这种软件工具可以帮助管理人员提高事务处理效率,达到事半功......
  • 洛谷 P3976 [TJOI2015] 旅游
    这出题人语言表达能力真的感人……希望你们看完这篇题解后不要觉得我的语言表达能力和出题人不相上下。题目大意给定一棵有点权的树,每次询问从\(u\)到\(v\)的路径上后经过的点权减去先经过的点权的最大值,再把这条路径上所有点的点权加上一个给定的数。分析俗话说得好:如果......
  • THUWC2024 旅游记
    洛谷博客没了之后我都不知道钓鱼博该传哪了。存一下THUPC2024记录:THUPC2024记录羟基计划我爱你(jijidawang,K8He,x383494)上来x383494把M过了.我扫了一遍好像K非常简单就写了,途中K8He秒了C.三发罚时过了K,开始睡觉.感觉会J了.醒了之后开始颓,过一会......
  • 洛谷 P9751 [CSP-J 2023] 旅游巴士 题解
    Solution能在起点等\(k\)的非负整数倍相当于能在任意点等\(k\)的非负整数倍。由于离开的时间要是\(k\)的负整数倍,将每个点拆成\(k\)个点,\(dis_{i,j}\)表示到了第\(i\)个点长度\(\bmod\text{}k\equivj\)的最短路径。转移时若时间未到,直接在原地等\(k\)的负整......
  • 基于SSM的旅游景点管理系统设计
    现代经济快节奏发展以及不断完善升级的信息化技术,让传统数据信息的管理升级为软件存储,归纳,集中处理数据信息的管理方式。本旅游景点管理系统就是在这样的大环境下诞生,其可以帮助管理者在短时间内处理完毕庞大的数据信息,使用这种软件工具可以帮助管理人员提高事务处理效率,达到事半功......