选择客栈算法题20220805

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

用来记录一下自己对这道题的理解,先用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数组才会开始记录各个色调的客栈数

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

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

 


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

853 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传