LeetCode高频题：客栈选择问题，总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚

LeetCode高频题：客栈选择问题，总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

文章目录

• LeetCode高频题：客栈选择问题，总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚
• • @[TOC](文章目录)
• 题目
• 一、审题
• 上述原文连接的解决方案
• 小根堆贪心解决
• • Cx2如何求？x中任选2个组合
  • 包装color和p为一个节点Node，然后准备小根堆的比较器
  • OK，解决输入npk，然后手撕代码，小根堆弹出节点，统计组合数量
• 还有一个尴尬的问题，上面我那个做法呀，因为排序漏掉了一个情况，比如5 2 7，其实住宿方案选择57，中间还有2可以喝咖啡，这个组合我没有算
• 总结

题目

丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示） ，且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈） ，且咖啡店的最低消费不超过 p。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。
————————————————
版权声明：本文为CSDN博主「流浪德意志」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/li4692625/article/details/121585585

一、审题

输入

第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
接下来的 n行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。

输出

输出只有一行，一个整数，表示可选的住宿方案的总数。

样例输入

5 2 3
0 5
1 3
0 2
1 4
1 5

样例输出

3

提示

2 人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，
但是若选择住 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。

上述原文连接的解决方案

怎么做的，我觉得没写特别清楚，有兴趣你去看看，代码c++的
代码很简单，但是精简，往往不是超级高手难以理解

下面我自己想一个好理解的方案

小根堆贪心解决

将每一行给你的color和p集合成一个客栈节点Node
把color和最低消费p整个为一个节点node，

然后整体放入小根堆自动排序，规则：color不同按照color升序，color相同的，按照p升序

然后遍历i=0–k-1每一个颜色

对于同一个色调i，先统计小根堆弹出的最低消费pi<=p的有几个x，然后看最低消费pi>p的弹出几个y?
那么i色调中组合方案就是x*y种

你想想是不是？

上图，对于0色调i来说，pi<=p=3的x=3种，也就是我们可以去这三家消费
而pi>p=3的就y=2种，我们只能从可以住的，与这些消费不起的店组合，即3*2=6种

对了，哈哈哈哈，在x种任选2家也是可以的！！！！！！！

ans=6+C3,2=6+3=9种

算法嘛就是在整理思路的过程中优化的！

好，我们整理一下，手撕代码：

Cx2如何求？x中任选2个组合

        //求组合CX2，好说//Ck2=k!/2!*(k-2)!  == k*(k-1)*(k-2)!/2*(k-2)!=k*(k-1)/2public static int Ck2(int k){if (k == 0 || k == 1) return 0;//如果k<2那不好意思，没得玩return k*(k - 1) >> 1;}

包装color和p为一个节点Node，然后准备小根堆的比较器

        //包装color和p节点public static class Node{public int color;public int p;public Node(int c, int pp){color = c;p = pp;}}//比较器——专门用来让小根堆按照规则排序的public static class colorComparator implements Comparator<Node>{@Overridepublic int compare(Node o1, Node o2){return o1.color == o2.color ? o1.p - o2.p : o1.color - o2.color;//color相同按p升序，不同按color升序}}

OK，解决输入npk，然后手撕代码，小根堆弹出节点，统计组合数量

        public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int[] nkp = new int[3];for (int i = 0; i < 3; i++) {nkp[i] = in.nextInt();}int n = nkp[0];int k = nkp[1];int p = nkp[2];//接下来n行，俩数PriorityQueue<Node> heap = new PriorityQueue<>(new colorComparator());for (int i = 0; i < n; i++) {int[] cp = new int[2];for (int j = 0; j < 2; j++) {cp[j] = in.nextInt();//读color和p}heap.add(new Node(cp[0], cp[1]));//加入堆}int ans = 0;//结果//然后开始处理统计每种颜色i=0--k-1上有啥情况for (int i = 0; i < k; i++) {int x = 0;//pi<=p的节点数量int y = 0;//pi>p的节点数量while (!heap.isEmpty() && heap.peek().color == i){//同一个色调弹出Node cur = heap.poll();if (cur.p <= p) x++;else y++;//2进1}//色调不同了，OK，统计ans += Ck2(x) + x * y;}//色调全部统计OKSystem.out.println(ans);}

测试：

5 2 3
0 5
1 3
0 2
1 4
1 5
3

完全OK
思路明确
可惜考试的时候，很紧张，没想出来招，尴尬，考试就是这样
慢慢想可能很好解决
但是临场考试，真的很难想到解决方案！！！
慢慢练习吧，见多识广！

还有一个尴尬的问题，上面我那个做法呀，因为排序漏掉了一个情况，比如5 2 7，其实住宿方案选择57，中间还有2可以喝咖啡，这个组合我没有算

这个问题是因为我认为排序导致的顺序问题

我们这样改进，把node再加一个因素：index，原始的客栈的位置

我们在弹出pi>p的时候，看看已经弹出x中，是否有一个在y的任意俩客栈间
这样的话，可以组合俩y

我们试试代码：

        public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int[] nkp = new int[3];for (int i = 0; i < 3; i++) {nkp[i] = in.nextInt();}int n = nkp[0];int k = nkp[1];int p = nkp[2];//接下来n行，俩数PriorityQueue<Node> heap = new PriorityQueue<>(new colorComparator());for (int i = 0; i < n; i++) {int[] cp = new int[2];for (int j = 0; j < 2; j++) {cp[j] = in.nextInt();//读color和p}heap.add(new Node(cp[0], cp[1], i));//加入堆,位置也标记}int ans = 0;//结果//然后开始处理统计每种颜色i=0--k-1上有啥情况for (int i = 0; i < k; i++) {int x = 0;//pi<=p的节点数量int y = 0;//pi>p的节点数量List<Integer> xHeap = new ArrayList<>();List<Integer> yHeap = new ArrayList<>();while (!heap.isEmpty() && heap.peek().color == i){//同一个色调弹出Node cur = heap.poll();if (cur.p <= p){x++;xHeap.add(cur.index);}else{y++;//2进1yHeap.add(cur.index);}}//色调不同了，OK，统计ans += Ck2(x) + x * y;//别忘了加俩y中一个x，那种合法的for(Integer index : xHeap){//挨个对比，看看有没有for (int j = 0; j < yHeap.size(); j++) {for (int l = j + 1; l < yHeap.size(); l++) {//枚举所有j l不同，看看是否满足同时夹住indexif ((yHeap.get(j) < index && index < yHeap.get(l)) ||(yHeap.get(l) < index && index < yHeap.get(j))) ans++;}}}}//色调全部统计OKSystem.out.println(ans);}//包装color和p节点public static class Node{public int color;public int p;public int index;public Node(int c, int pp, int i){color = c;p = pp;index = i;}}

测试一把;

3 1 3
0 5
0 2
0 5

这次OK了
上面2 5，2 5， 5 5 都行的
就是复杂度高了点感觉

3 1 3
0 5
0 2
0 5
3

结果是OK的

但是还得想想别的办法

总结

提示：重要经验：

1）客栈问题是很经典的题目，贪心，然后统计可以组合的方案
2）贪心的题目就是小根堆加排序解决的，老油条了
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。