Java的贪心和枚举怎么使用

王林 2023-05-20 11:46 1216浏览转载

笔试技巧：学会根据数据范围猜知识点

一般1s 时间限制的题目，时间复杂度能跑到 1e8 左右（ python 和 java 会少一些，所以建议大家使用c/c++ 做笔试题）。

n 范围 20 以内：	O(n*2^n)	状压搜索 /dfs 暴搜
n 范围 200 以内：	O(n^3)	三维 dp
n 范围 3000 以内：	O(n^2)	二维 dp 背包枚举二维前缀和等
n 范围 1e5 以内：	O(n√n)	暴力求因子等
n 范围 1e6 以内：	O(nlogn)	二分答案使用各种 stl 并查集欧拉筛等
n 范围 1e7 以内：	O(n)	双指针线性 dp 差分 / 前缀和
n 范围 1e14 以内：	O(√n)	求约数和约数个数

贪心：

贪心指每一步都做出当前最优的选择。一般解决的问题有如下特点：局部最优能导致全局最优。

请注意，贪心并不是万能的！

有n个物品。每个物品有价值v[i]，以及重量w[i]。

现在取总重量不超过m的物品，问取的物品价值最大是多少？（背包问题）

策略1：按照价值降序排列，每次取价值最高的。
策略2 ：按照重量升序排列，每次取重量最轻的。
策略3 ：按照价值/重量（即单位价值）降序排列，每次取单位价值最高的。

枚举：

1.朴素枚举

顾名思义，用for循环枚举所有情况。

2.状压枚举

借助n进制的性质进行枚举。

适合场景：共有n个物品，每个物品有m种状态，枚举所有物品的所有状态，复杂度为O(m^n)。

二进制状压枚举的写法：

经典问题：给定n个数a1、a2……an，每个数可选可不选，列举所有可能的方案。

for(int i=0;i<h3>算法题1：</h3><p>chika和蜜柑（PriorityQueue+Comparator的使用）</p><p>难度 ⭐⭐</p><p>chika很喜欢吃蜜柑。每个蜜柑有一定的酸度和甜度，chika喜欢吃甜的，但不喜欢吃酸的。</p><p>Chika吃了k个蜜柑，总共有n个蜜柑，她将计算所吃蜜柑的甜度和酸度之和。chika想获得尽可能大的甜度总和。如果有多种方案，她希望总酸度尽可能小。</p><p>她想知道，最终的总酸度和总甜度是多少？</p><p>题目信息：先按甜度降序排序，后按酸度升序排序（保持之前的甜度降序排序优先，酸度升序排序次之） </p><p>输入描述:</p><p>第一行有两个正整数n和k，分别代表蜜柑总数和chika吃的蜜柑数量。(1≤k≤n≤200000)</p><p>第二行有n个正整数ai，分别代表每个蜜柑的酸度。（1≤ai≤1e9）</p><p>第二行有n个正整数bi，分别代表每个蜜柑的甜度。（1≤bi≤1e9）</p><p>输出描述:</p><p>两个正整数，用空格隔开。分别表示总酸度和总甜度。</p><h4>示例</h4><p>输入</p><blockquote>3 21 3 42 2 5</blockquote><p>输出</p><blockquote><p>5 7</p></blockquote><p>说明</p><p>选择1号和3号蜜柑，总酸度为5，总甜度为7，为最优解。</p><pre class="brush:java;">import java.io.*;
import java.util.*;
public class Main{
    public static class Orange{
            int acid;
            int sweet;
            public Orange(int acid, int sweet){
                this.acid = acid;
                this.sweet = sweet;
            }
            public Orange(){}
        }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = br.readLine().split(" ");
        int n = Integer.parseInt(tmp[0]);
        int k = Integer.parseInt((tmp[1]));
        String[] ai = br.readLine().split(" ");
        String[] bi = br.readLine().split(" ");
        //定义一个优先队列，并根据指定的比较器对其元素进行排序。
        PriorityQueue<orange> queue = new PriorityQueue((Orange o1, Orange o2)->{
            //匿名内部类以lambda的形式定义排序规则
            if(o1.sweet == o2.sweet){
                return o1.acid - o2.acid;
            }else{
                return o2.sweet - o1.sweet;
            }
        });
        for(int i = 0; i <p>目的：</p>
<p>了解什么是贪心，当设计到优先级时可以考虑使用PriorityQueue+Comparator。</p>
<h3>算法题2：</h3>
<p>you和帆船 </p>
<p>难度 ⭐⭐</p>
<p>you的父亲是一名船长。因此you从小就很喜欢大海。这天，她乘着一艘帆船出发了。</p>
<p>大海上有很多宝藏，每个宝藏的坐标是已知的。you的初始坐标是（0,0）。她想探索两个宝藏，然后回到初始点。</p>
<p>you希望航线尽可能短。她想知道，最短航线的长度是多少？</p>
<p>题目信息：两个for循环枚举一下，再保存最短路径即可。</p>
<p>输入描述:</p>
<p>第一行一个正整数n，代表宝藏的数量。（2≤n≤2000）</p>
<p>接下来的n行，每行2个正整数xi，yi，代表第i个宝藏的坐标（-3000≤xi,yi≤3000）</p>
<p>不保证不存在两个宝藏位置相同。意思是，you可以在同一个位置探索这两个宝藏。</p>
<p>输出描述:</p>
<p>最短路线的长度。小数点后保留6位。</p>
<h4>示例</h4>
<p>输入</p>
<blockquote>
<p>2</p>
<p>1 0</p>
<p>0 1</p>
</blockquote>
<p>输出</p>
<blockquote><p>3.414214</p></blockquote>
<p>说明</p>
<p><img src="https://img.php.cn/upload/article/000/465/014/168455440995490.png?x-oss-process=image/resize,p_40" alt="Java的贪心和枚举怎么使用"></p>
<pre class="brush:java;">import java.io.*;
import java.util.*;
 
class Point{
    double x;
    double y;
}
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Point[] points = new Point[n];
        for(int i=0;i<n><p>目的：</p>
<p>了解什么是枚举，虽然是一个一个列举，但是结合实际还是有优化的方式。</p>
<p>比如此题两层循环只枚举了一半的情况：因为所求的是距离，跟两个端点无关。</p>
<p>思考：</p>
<p>假如不止有两个宝箱需要被获取，那么应该怎么办？？？下一题可以参考一下。</p>
<h3>算法题3： </h3>
<p>数位染色   </p>
<p>难度 ⭐⭐⭐</p>
<p>小红拿到了一个正整数 X 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。</p>
<p>她不知道能不能达成目标。你能告诉她吗？</p>
<p>输入描述:</p>
<p>一个正整数X ，1</p>
<p>输出描述:</p>
<p>输出"Yes"是在小红能够按要求完成染色的前提下。否则输出"No"。</p>
<h4>示例1</h4>
<p>输入</p>
<blockquote><p>1234567</p></blockquote>
<p>输出</p>
<blockquote><p>Yes</p></blockquote>
<p>说明</p>
<p>将3、4、7染成红色即可，这样3+4+7=1+2+5+6</p>
<h4>示例2</h4>
<p>输入</p>
<blockquote><p>23</p></blockquote>
<p>输出</p>
<blockquote><p>No</p></blockquote>
<p>说明</p>
<p>显然无论如何都不能完成染色。</p>
<pre class="brush:java;">import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long x= Long.parseLong(br.readLine());
        //循环0到2^18来展现所有的可能性
        for(int i=0;i<p>这题使用的是状压枚举</p><p>只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）</p><pre class="brush:java;"> for(int i=0;i<p>当然这题也可以使用背包或dfs来解答。</p><h3>算法题4： </h3><p>ranko的手表  </p><p>难度 ⭐⭐⭐⭐</p><p>ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。</p><p>Ranko checked the time at t1 and then again at t2 after some time had passed.。她想弄清楚t1和t2两个时间点之间的最大和最小时间间隔是多少</p><p>保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。 </p><p>输入描述:</p><p>两行输入两个时间，为 xx:xx 的形式。x可以是数字或字符'?'，当为'?'时表示该数字未显示。保证输入是合法的。</p><p>输出描述:</p><p>一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。</p><h4>示例1</h4><p>输入</p><blockquote>
<p>18:0?</p>
<p>2?:1?</p>
</blockquote><p>输出</p><blockquote><p>121 319</p></blockquote><p>说明</p><p>相距最小的时间为 18:09 到 20:10 ，相距121分钟。</p><p>相距最大的时间为 18:00 到 23:19 ，相距319分钟。</p><pre class="brush:java;">import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        ArrayList<integer> a1 = new ArrayList();
        ArrayList<integer> a2 = new ArrayList();
        for(int i = 0; i </integer></integer>