问题描述
丽江河边有n家独具特色的客栈,按照位置从1到n编号。每家客栈装饰有k种不同的色调(用整数0 ~ k-1表示),并且每家客栈都设有一家咖啡店,每个咖啡店都有各自的最低消费。两位游客喜欢相同的色调,并计划分别住在两家色调相同的客栈中。他们打算在晚上选择一家位于两家客栈之间(包括住的客栈)的咖啡店喝咖啡,要求咖啡店的最低消费不超过p元。他们想知道总共有多少种选择住宿的方案,确保晚上可以找到一家最低消费不超过p元的咖啡店。
输入格式
输入文件共包含n+1行。
第一行包含三个整数n, k, p,每两个整数之间用一个空格隔开,分别表示客栈的数量、色调的数量和能接受的最低消费的最高值。
接下来的n行,第i+1行包含两个整数,表示第i号客栈的装饰色调和该客栈咖啡店的最低消费。
输出格式
输出仅一行,包含一个整数,表示可选的住宿方案的总数。
样例输入
5 2 3
0 5
1 3
0 2
1 4
1 5
样例输出
3
提示
【样例说明】
客栈编号:① ② ③ ④ ⑤
色调:0 1 0 1 1
最低消费:5 3 2 4 5
两人要住同样色调的客栈,所有可选的住宿方案包括:住客栈①③,②④,②⑤,④⑤,但若选择住4、5号客栈,则4、5号客栈之间的咖啡店最低消费为4元,而两人能承受的最低消费是3元,所以不满足要求。因此只有前3种方案可选。
数据范围:
对于30%的数据,n ≤ 100;
对于50%的数据,n ≤ 1,000;
对于100%的数据,2 ≤ n ≤ 200,000,0 ≤ k ≤ 50,0 ≤ p ≤ 100,0 ≤ 最低消费 ≤ 100。
解题思路
一种较为直观的算法是使用线段树查询区间最值,但这会导致较高的时间复杂度。我们寻求更高效的解法。
对于每个客栈i,如果它前面有与其同色的客栈j,我们可以从离i最近的第一个开始往远处找,只要某一个满足到i之间花费的最小值小于要求值,则往远处延伸的都满足条件。
因此,我们记录与i同色的上一个点位置pos和花费小于要求值点离i最近的点last。如果pos <= last,则i可以和前面搭配的数量ans_i = cnt[col_i],否则ans_i = ans_pos。
以下是实现代码:
#include
#include
-
本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!----- ... [详细]本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]本题通过将每个矩形视为一个节点,根据其相对位置构建拓扑图,并利用深度优先搜索(DFS)或状态压缩动态规划(DP)求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]使用GDI的一些AIP函数我们可以轻易的绘制出简 ... [详细]本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]Tags | 热门标签RankList | 热门文章
- 1cgo+gSoap+onvif学习总结:1、方案初衷、资料收集及cgo实现helloworld
- 2fpga板制作调试过程记录
- 3launch.json配置php,launchjson有什么用
- 4有没有更好的方法来编写这个VBA代码?
- 5PySparkDataFrame过滤嵌套列
- 6群晖docker安装nginx,docker安装黑群晖
- 7干货!基于元学习的内容定向推广
- 8Linux配置SSH远程登录管理
- 9卡苹果6plus在线_江苏一卡通推出NFC全卡“金陵通沃卡”,苹果手机也能用
- 10跨域请求数据报错Unexpected token :如何解决
- 11Foresight Ventures 市场周报:美联储偏鸽,巨鲸拉高出货
- 12node-express(1)使用post和get方法解决跨域问题
- 13javascript中方法名区分大小写吗
- 14记一次线上redis报错(JedisExhaustedPoolException: Could not get a resource since the pool is exhausted)
- 15cdw5121jsqha2r4(CDW5041TPBHA1R5)