LeetCode高频题：客栈选择问题，总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的...
时间：2022-11-19 10:00:00
LeetCode高频问题：客栈的选择有多少种住宿方案，以确保最低消费不超过晚上 p 元咖啡店小聚
提示：本题为系列LeetCode150道高频题，你未来遇到的互联网厂商的笔试和面试题，基本都是改编自这个题目的
互联网大厂商在公司养了大量的ACM比赛的老板们，晚饭后，他们会设计试题，然后参加考试。你要做的就是学习基础树的结构和算法，然后打开任督的第二个脉搏，以应对大厂的笔试面试问题！
如果你不扎实地学习数据结构和算法，撕开代码，锻炼解决问题的能力，你甚至可能不理解笔试面试中的问题！例如，华为，字节等等，足以让你不理解问题
文章目录
- LeetCode高频问题：客栈的选择有多少种住宿方案，以确保最低消费不超过晚上 p 元咖啡店小聚
-
- @[TOC](文章目录)
- 题目
- 一、审题
- 上述原文连接的解决方案
- 贪心解决小根堆
-
- Cx2如何求？x中选两个组合
- 包装color和p为一个节点Node，然后准备小根堆的比较器
- OK，解决输入npk，然后手撕代码，小根堆弹出节点，统计组合数量
- 还有一个尴尬的问题，上面我的做法，因为排名错过了一种情况，比如5 2 7.其实住宿计划是57，中间有2个可以喝咖啡。我没有计算这个组合
- 总结
文章目录
- LeetCode高频问题：客栈的选择有多少种住宿方案，以确保最低消费不超过晚上 p 元咖啡店小聚
-
- @[TOC](文章目录)
- 题目
- 一、审题
- 上述原文连接的解决方案
- 贪心解决小根堆
-
- Cx2如何求？x中选两个组合
- 包装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=也就是说，我们可以去这三家公司消费
而pi>p=3的就y=有两种，我们只能与这些负担不起的商店结合，即3*2=6种
对了，哈哈哈哈，也可以在x种中选择两个！
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)/2 public 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>
{
@Override
public
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;
}
//色调全部统计OK
System.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进1
yHeap.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不同，看看是否满足同时夹住index
if ((yHeap.get(j) < index && index < yHeap.get(l)) ||
(yHeap.get(l) < index && index < yHeap.get(j))) ans++;
}
}
}
}
//色调全部统计OK
System.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，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
