P1311 选择客栈【洛谷算法习题】

P1311 选择客栈网页链接P1311 选择客栈题目描述丽江河边有n nn家很有特色的客栈客栈按照其位置顺序从1 11到n nn编号。每家客栈都按照某一种色调进行装饰总共k kk种用整数0 ∼ k − 1 0 \sim k-10∼k−1表示且每家客栈都设有一家咖啡店每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游他们喜欢相同的色调又想尝试两个不同的客栈因此决定分别住在色调相同的两家客栈中。晚上他们打算选择一家咖啡店喝咖啡要求咖啡店位于两人住的两家客栈之间包括他们住的客栈且咖啡店的最低消费不超过p pp。他们想知道总共有多少种选择住宿的方案保证晚上可以找到一家最低消费不超过p pp元的咖啡店小聚。输入格式共n 1 n1n1行。第一行三个整数n , k , p n, k, pn,k,p每两个整数之间用一个空格隔开分别表示客栈的个数色调的数目和能接受的最低消费的最高值接下来的n nn行第i 1 i1i1行两个整数之间用一个空格隔开分别表示 $i $ 号客栈的装饰色调a i a_iai​和i ii号客栈的咖啡店的最低消费b i b_ibi​。输出格式一个整数表示可选的住宿方案的总数。输入输出样例 #1输入 #15 2 3 0 5 1 3 0 2 1 4 1 5输出 #13说明/提示样例解释2 人要住同样色调的客栈所有可选的住宿方案包括住客栈①③②④②⑤④⑤但是若选择住4 , 5 4,54,5号客栈的话4 , 5 4,54,5号客栈之间的咖啡店的最低消费是4 44而两人能承受的最低消费是3 33元所以不满足要求。因此只有前3 33种方案可选。数据范围对于 $30% $ 的数据有n ≤ 100 n \leq 100n≤100对于 $50% $ 的数据有n ≤ 1 000 n \leq 1\,000n≤1000对于100 % 100\%100%的数据有2 ≤ n ≤ 2 × 10 5 2 \leq n \leq 2 \times 10^52≤n≤2×1051 ≤ k ≤ 50 1 \leq k \leq 501≤k≤500 ≤ p ≤ 100 0 \leq p \leq 1000≤p≤1000 ≤ b i ≤ 100 0 \leq b_i \leq 1000≤bi​≤100。解题思路本题核心是线性遍历分组计数依托色调数量极少k ≤ 50 k≤50k≤50的特性实现极致优化。遍历客栈时实时记录最近一个最低消费≤p的客栈位置now对每种色调分别维护该色调已出现的客栈总数、上一次合法配对的基准位置。若当前同色调的上一个客栈位置在now左侧说明两客栈之间存在合法咖啡店直接累加该色调的合法配对数。全程仅需一次线性遍历时间复杂度O ( n ) O(n)O(n)无冗余计算完美适配n ≤ 2 × 10 5 n≤2×10^5n≤2×105的大数据约束快速统计所有合法方案数。总结核心逻辑以最近合法咖啡店为分界点统计同色调且满足位置条件的客栈配对数。关键操作记录最近合法位置、按色调分组维护计数、线性遍历累加答案。效率保障单遍遍历常数级操作高效处理大规模数据无超时风险。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll maxn200005;ll n,k,p;ll color,price;ll last[maxn];ll sum[maxn];ll cnt[maxn];ll ans0;ll now;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnkp;for(ll i1;in;i){cincolorprice;if(pricep)nowi;if(nowlast[color])sum[color]cnt[color];last[color]i;anssum[color];cnt[color];}coutansendl;return0;}