2597. 「NOIP2011」选择客栈

题意

有$n$个客栈,每个客栈都配有咖啡馆。有两名旅客想住在同色调的客栈中,又想在两客栈之间的咖啡馆中小聚,咖啡馆的价钱不能高于$p$。 对于 $100\%$ 的数据,有 $2\leq n\leq2\times 10^6$,$0<k\leq10^4$ ,$0\leq p\leq100$,$0\leq$ 最低消费 $\leq100$ 。

思路

$n$的范围那么大,$k$的范围那么小。那么暴力吧。 设$h_i$表示目前颜色$i$的客栈数量,$las_i$表示最近的颜色为$i$的客栈的编号。 然后$O(n)$扫一遍就好了啊。
暂无评论

发送评论


				
上一篇
下一篇