选择客栈算法题20220805

用来记录一下自己对这道题的理解,先用java编写,代码逻辑是互通的。

题目链接:https://www.luogu.com.cn/problem/P1311

题解链接:https://www.luogu.com.cn/problem/solution/P1311(题解码字有误,建议配合代码阅读)

public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 int n,k,p,t,ans,price;
 ans = 0;
 t = 0;
 // n个客栈 k个色调 有p块钱
 n = scanner.nextInt(); //客栈
 k = scanner.nextInt(); //色调
 p = scanner.nextInt(); //最低消费
 int[] num = new int[k+1]; //用来记录颜色对应客栈有多少个
 int[] color = new int[n+1]; //用来记录每个客栈的颜色属性
 System.out.println("------------------------------");
 for(int i=1;i<=n;i++)
 {
 color[i] = scanner.nextInt();
 price = scanner.nextInt();
 if(price <= p)
 {
 //当碰到符合最低消费时,开始记录前面的客栈数到num数组中
 for(int j = i; j > t; j--)
 num[color[j]]++; //开始记录前面的客栈数
 t = i; //更新最后一个符合最低消费的位置
 ans += num[color[i]]-1; //减去本身
 }
 else
 ans += num[color[i]];
 System.out.println(Arrays.toString(num) + " | " + Arrays.toString(color) + " | " + ans);
 }
 System.out.printf("%d",ans);
 }

ans就是总方案数结果,其实核心就是下面这两句来统计选择方案,按照第二个客栈来选择第一个客栈。

ans+=num[color[i]]-1;

ans+=num[color[i]];

===因为只需要两个客栈之间有最低消费就可以,所以每个第二个客栈可选择的客栈都是前面所有相同色调的客栈===

选择的前提

1有出现最低消费客栈,只有当出现了最低消费的客栈num数组才会开始记录各个色调的客栈数

2第二个客栈与第一个客栈色调相同

3如果第二个客栈是最低消费客栈,要减去本身

• 编辑
• 预览