选择客栈算法题20220805

hld789123 · · 1611 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

用来记录一下自己对这道题的理解，先用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]];

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

选择的前提

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

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

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