热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

丽江客栈选择问题

本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。

问题描述

丽江河边有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
#include
#include
#include
#include
#include
#include
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;i++)
#define per(i,a,b) for(RG i=a;i>=b;i--)
#define ll long long
#define inf (1<<30)
#define maxn 200005
#define maxk 55
using namespace std;
ll n,m,lim,ans;
ll sum[maxn],cnt[maxk],last[maxk];
int col,val,laok,lasame;
inline int read() {
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main() {
n=read(),m=read(),lim=read();
rep(i,1,n) {
col=read(),val=read();
lasame=last[col];
if(val<=lim) laok=i;
if(lasame<=laok) sum[i]=cnt[col];
else sum[i]=sum[lasame];
cnt[col]++,last[col]=i;ans+=sum[i];
}
cout< return 0;
}

推荐阅读
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如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算法进行求解。 ... [详细]
  • 在多线程编程环境中,线程之间共享全局变量可能导致数据竞争和不一致性。为了解决这一问题,Linux提供了线程局部存储(TLS),使每个线程可以拥有独立的变量副本,确保线程间的数据隔离与安全。 ... [详细]
  • 微软Exchange服务器遭遇2022年版“千年虫”漏洞
    微软Exchange服务器在新年伊始遭遇了一个类似于‘千年虫’的日期处理漏洞,导致邮件传输受阻。该问题主要影响配置了FIP-FS恶意软件引擎的Exchange 2016和2019版本。 ... [详细]
author-avatar
wocanimagebi
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有