【每日一题】9月4日题目精讲-选择客栈

每日一题暑期活动获奖名单~
sunsetcolors
zzugzx
回归梦想​
blowhail
hnust_yangyanjun
jxnu-19-软技一班-刘晟
求求大佬带带我emm
昵称很长很长真是太好了
以上同学在暑假期间写够30篇题解，获得牛客T恤，三个工作日内，牛客工作人员将通过牛客消息处与你沟通寄送地址~

题号 NC16594
名称 选择客栈
来源 NOIP2011提高组复赛
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

枚举右边一个客栈r，考虑左边有多少个可以选的客栈。
那么左边可选的客栈l需要满足两个条件：
1.[l,r]区间内有某个咖啡店花费小于p
2.和r颜色一样
那么我们可以用coffe[i]维护出i之前离i最近的花费小于p的咖啡店，显然当b[i]<=p时，coffe[i]=i否则coffe[i]=coffe[i-1]。
是coffe[r]及其之前的客栈都满足到r之间的咖啡店最低消费小于等于p了，于是我们现在就是求coffe[r]及其左边和r一样的客栈的个数，这个只需要维护出每个点之前每个颜色的客栈个数即可。
（由于r增大的时候coffe[r]只增不减，实现上可以类似双指针写法，这样存每个颜色的客栈个数的数组可以开成一维）

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目9月11日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴