首页 > 代码库 > 选择客栈
选择客栈
【题目描述】
丽江边有n家客栈，客栈按照其位置顺序从1~n编号。每家客栈都按某一种色调进行装饰（总共k种，用0~k-1表示），且每家客栈都有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们分别住在色调相同的两家客栈中，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。
现询问总共有多少种住宿的方案，保证可以找到一家最低消费不超过p元的咖啡店。
【输入描述】
输入n+1行。
第一行输入三个整数n、k、p，分别表示客栈总数、色调总数和两人能接受的最低消费的最高值；
接下来n行，每行输入两个整数，分别表示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 ≤ 1000；
对于100%的数据，2 ≤ n ≤ 200000，0 < k ≤ 50，0 ≤ p ≤ 100，0 ≤ 最低消费 ≤ 100。
源代码：#include<cstdio>int N,K,P,Place,Ans,i[50],Num[50],Sum[50];int main(){ scanf("%d%d%d",&N,&K,&P); for (int a=1;a<=N;a++) { int C,M; scanf("%d%d",&C,&M); if (M<=P) //消费符合条件，记录当前位置。 Place=a; if (Place>=i[C]) //为什么要加这个判断呢？注意，Place有时才更新，i[]每次都更新。一开始脑残觉得加不加这个判断都无所谓，然后就10分蛤蛤蛤。 Sum[C]=Num[C]; //Sum[]表示某颜色对于当前点符合条件的客栈数量，Num[]表示客栈数量。 i[C]=a; //更新位置。 Ans+=Sum[C]; Num[C]++; //更新总数。 } printf("%d",Ans); return 0;}/* 烧脑的模拟题。 利用了乘法原理，仔细想想会发现，在for()中如此处理并不会漏下什么。*/
选择客栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。