四个实例超详细讲解Java 贪心和枚举的特点与使用

四个实例超详细讲解Java 贪心和枚举的特点与使用

目录贪心：枚举：1.朴素枚举2.状压枚举   算法题1：示例算法题2：示例算法题3： 示例1示例2算法题4： 示例

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

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

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

贪心：

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

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

有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<1<

int p=i; //先将i取出

int sum=0; //用一个变量维护取出的数之和

for(j=0;j

sum+=p%2*a[j]; //这句话是求取出来的数之和。p%2为对应二进制位

//这里也可以进行其他操作，不一一举例。

p/=2; //求下一个二进制位

}

//这里可以添加想要的操作。

}

算法题1：

chika和蜜柑（PriorityQueue+Comparator的使用）

难度 ⭐⭐

chika很喜欢吃蜜柑。每个蜜柑有一定的酸度和甜度，chika喜欢吃甜的，但不喜欢吃酸的。

一共有n个蜜柑，chika吃k个蜜柑，将获得所吃的甜度之和与酸度之和。chika想获得尽可能大的甜度总和。如果有多种方案，她希望总酸度尽可能小。

她想知道，最终的总酸度和总甜度是多少？

题目信息：先按甜度降序排序，后按酸度升序排序（保持之前的甜度降序排序优先，酸度升序排序次之）

输入描述:

第一行有两个正整数n和k，分别代表蜜柑总数和chika吃的蜜柑数量。(1≤k≤n≤200000)

第二行有n个正整数ai，分别代表每个蜜柑的酸度。（1≤ai≤1e9）

第二行有n个正整数bi，分别代表每个蜜柑的甜度。（1≤bi≤1e9）

输出描述:

两个正整数，用空格隔开。分别表示总酸度和总甜度。

示例

输入

3 2

1 3 4

2 2 5

输出

5 7

说明

选择1号和3号蜜柑，总酸度为5，总甜度为7，为最优解。

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 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 < n; i++){

Orange orange = new Orange();

orange.acid = Integer.parseInt(ai[i]);

orange.sweet = Integer.parseInt(bi[i]);

queue.add(orange);

}

long totalAcid = 0;

long totalSweet = 0;

for(int i = 0; i < k; i++){

Orange o = queue.poll();

totalAcid += o.acid;

totalSweet += o.sweet;

}

System.out.println(totalAciRQqoRfBqd + " " + totalSweet);

}

}

目的：

了解什么是贪心，当设计到优先级时可以考虑使用PriorityQueue+Comparator。

算法题2：

you和帆船

难度 ⭐⭐

you的父亲是一名船长。因此you从小就很喜欢大海。这天，她乘着一艘帆船出发了。

大海上有很多宝藏，每个宝藏的坐标是已知的。you的初始坐标是（0,0）。她想探索两个宝藏，然后回到初始点。

you希望航线尽可能短。她想知道，最短航线的长度是多少？

题目信息：两个for循环枚举一下，再保存最短路径即可。

输入描述:

第一行一个正整数n，代表宝藏的数量。（2≤n≤2000）

接下来的n行，每行2个正整数xi，yi，代表第i个宝藏的坐标（-3000≤xi,yi≤3000）

不保证不存在两个宝藏位置相同。意思是，you可以在同一个位置探索这两个宝藏。

输出描述:

最短路线的长度。小数点后保留6位。

示例

输入

2

1 0

0 1

输出

3.414214

说明

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

String[] strings = br.readLine().split(" ");

Point point = new Point();

point.x = Integer.parseInt(strings[0]);

point.y = Integer.parseInt(strings[1]);

points[i] = point;

}

double min = Double.MAX_VALUE;//定义最大值，寻找较小值

//双层遍历枚举

for (int i=0;i

for (int j=i+1;j

double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)

+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)

+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));

min = Math.min(min, temp);

}

}

System.out.println(String.format("%.6f", min));

}

}

目的：

了解什么是枚举，虽然是一个一个列举，但是结合实际还是有优化的方式。

比如此题两层循环只枚举了一半的情况：因为所求的是距离，跟两个端点无关。

思考：

假如不止有两个宝箱需要被获取，那么应该怎么办？？？下一题可以参考一下。

算法题3：

数位染色

难度 ⭐⭐⭐

小红拿到了一个正整数 X 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。

她不知道能不能达成目标。你能告诉她吗？

输入描述:

一个正整数X ，1<= X <=10^18

输出描述:

如果小红能按要求完成染色，输出"Yes"。否则输出"No"。

示例1

输入

1234567

输出

Yes

说明

将3、4、7染成红色即可，这样3+4+7=1+2+5+6

示例2

输入

23

输出

No

说明

显然无论如何都不能完成染色。

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<1<<19;i++){

long p=i,s1=0,s2=0,temp=x;

//将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。

for(int j=0;j<19;j++){

if(p%2==1)s1+=temp%10;

else s2+=temp%10;

p/=2;

temp/=10;

}

if(s1==s2){

System.out.println("Yes");

System.exit(0);

}

}

System.out.println("No");

}

}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

for(int i=0;i<1<<19;i++)

//修改成

for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;

for(int i=0;i

当然这题也可以使用背包或dfs来解答。

算法题4：

ranko的手表

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

ranko 在 t1 时刻看了下时间，过了一段时间在 t2 时刻看了下时间。她想知道， t1  和t2这两个时刻之间相距的时间的最大值和最小值是多少？

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。

输入描述:

两行输入两个时间，为 xx:xx 的形式。其中 x 为数字或者字符 '?' ，问号代表这个数字没有显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

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 a1 = new ArrayList<>();

ArrayList a2 = new ArrayList<>();

for(int i = 0; i < 60*24; i++){

int hour = i/60, minute = i%60;

if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&

(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&

(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&

(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);

if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&

(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&

(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&

(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);

}

int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for(int i = 0; i

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

int p=i; //先将i取出

int sum=0; //用一个变量维护取出的数之和

for(j=0;j

sum+=p%2*a[j]; //这句话是求取出来的数之和。p%2为对应二进制位

//这里也可以进行其他操作，不一一举例。

p/=2; //求下一个二进制位

}

//这里可以添加想要的操作。

}

算法题1：

chika和蜜柑（PriorityQueue+Comparator的使用）

难度 ⭐⭐

chika很喜欢吃蜜柑。每个蜜柑有一定的酸度和甜度，chika喜欢吃甜的，但不喜欢吃酸的。

一共有n个蜜柑，chika吃k个蜜柑，将获得所吃的甜度之和与酸度之和。chika想获得尽可能大的甜度总和。如果有多种方案，她希望总酸度尽可能小。

她想知道，最终的总酸度和总甜度是多少？

题目信息：先按甜度降序排序，后按酸度升序排序（保持之前的甜度降序排序优先，酸度升序排序次之）

输入描述:

第一行有两个正整数n和k，分别代表蜜柑总数和chika吃的蜜柑数量。(1≤k≤n≤200000)

第二行有n个正整数ai，分别代表每个蜜柑的酸度。（1≤ai≤1e9）

第二行有n个正整数bi，分别代表每个蜜柑的甜度。（1≤bi≤1e9）

输出描述:

两个正整数，用空格隔开。分别表示总酸度和总甜度。

示例

输入

3 2

1 3 4

2 2 5

输出

5 7

说明

选择1号和3号蜜柑，总酸度为5，总甜度为7，为最优解。

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 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 < n; i++){

Orange orange = new Orange();

orange.acid = Integer.parseInt(ai[i]);

orange.sweet = Integer.parseInt(bi[i]);

queue.add(orange);

}

long totalAcid = 0;

long totalSweet = 0;

for(int i = 0; i < k; i++){

Orange o = queue.poll();

totalAcid += o.acid;

totalSweet += o.sweet;

}

System.out.println(totalAciRQqoRfBqd + " " + totalSweet);

}

}

目的：

了解什么是贪心，当设计到优先级时可以考虑使用PriorityQueue+Comparator。

算法题2：

you和帆船

难度 ⭐⭐

you的父亲是一名船长。因此you从小就很喜欢大海。这天，她乘着一艘帆船出发了。

大海上有很多宝藏，每个宝藏的坐标是已知的。you的初始坐标是（0,0）。她想探索两个宝藏，然后回到初始点。

you希望航线尽可能短。她想知道，最短航线的长度是多少？

题目信息：两个for循环枚举一下，再保存最短路径即可。

输入描述:

第一行一个正整数n，代表宝藏的数量。（2≤n≤2000）

接下来的n行，每行2个正整数xi，yi，代表第i个宝藏的坐标（-3000≤xi,yi≤3000）

不保证不存在两个宝藏位置相同。意思是，you可以在同一个位置探索这两个宝藏。

输出描述:

最短路线的长度。小数点后保留6位。

示例

输入

2

1 0

0 1

输出

3.414214

说明

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

String[] strings = br.readLine().split(" ");

Point point = new Point();

point.x = Integer.parseInt(strings[0]);

point.y = Integer.parseInt(strings[1]);

points[i] = point;

}

double min = Double.MAX_VALUE;//定义最大值，寻找较小值

//双层遍历枚举

for (int i=0;i

for (int j=i+1;j

double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)

+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)

+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));

min = Math.min(min, temp);

}

}

System.out.println(String.format("%.6f", min));

}

}

目的：

了解什么是枚举，虽然是一个一个列举，但是结合实际还是有优化的方式。

比如此题两层循环只枚举了一半的情况：因为所求的是距离，跟两个端点无关。

思考：

假如不止有两个宝箱需要被获取，那么应该怎么办？？？下一题可以参考一下。

算法题3：

数位染色

难度 ⭐⭐⭐

小红拿到了一个正整数 X 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。

她不知道能不能达成目标。你能告诉她吗？

输入描述:

一个正整数X ，1<= X <=10^18

输出描述:

如果小红能按要求完成染色，输出"Yes"。否则输出"No"。

示例1

输入

1234567

输出

Yes

说明

将3、4、7染成红色即可，这样3+4+7=1+2+5+6

示例2

输入

23

输出

No

说明

显然无论如何都不能完成染色。

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<1<<19;i++){

long p=i,s1=0,s2=0,temp=x;

//将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。

for(int j=0;j<19;j++){

if(p%2==1)s1+=temp%10;

else s2+=temp%10;

p/=2;

temp/=10;

}

if(s1==s2){

System.out.println("Yes");

System.exit(0);

}

}

System.out.println("No");

}

}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

for(int i=0;i<1<<19;i++)

//修改成

for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;

for(int i=0;i

当然这题也可以使用背包或dfs来解答。

算法题4：

ranko的手表

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

ranko 在 t1 时刻看了下时间，过了一段时间在 t2 时刻看了下时间。她想知道， t1  和t2这两个时刻之间相距的时间的最大值和最小值是多少？

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。

输入描述:

两行输入两个时间，为 xx:xx 的形式。其中 x 为数字或者字符 '?' ，问号代表这个数字没有显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

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 a1 = new ArrayList<>();

ArrayList a2 = new ArrayList<>();

for(int i = 0; i < 60*24; i++){

int hour = i/60, minute = i%60;

if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&

(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&

(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&

(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);

if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&

(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&

(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&

(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);

}

int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for(int i = 0; i

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

sum+=p%2*a[j]; //这句话是求取出来的数之和。p%2为对应二进制位

//这里也可以进行其他操作，不一一举例。

p/=2; //求下一个二进制位

}

//这里可以添加想要的操作。

}

算法题1：

chika和蜜柑（PriorityQueue+Comparator的使用）

难度 ⭐⭐

chika很喜欢吃蜜柑。每个蜜柑有一定的酸度和甜度，chika喜欢吃甜的，但不喜欢吃酸的。

一共有n个蜜柑，chika吃k个蜜柑，将获得所吃的甜度之和与酸度之和。chika想获得尽可能大的甜度总和。如果有多种方案，她希望总酸度尽可能小。

她想知道，最终的总酸度和总甜度是多少？

题目信息：先按甜度降序排序，后按酸度升序排序（保持之前的甜度降序排序优先，酸度升序排序次之）

输入描述:

第一行有两个正整数n和k，分别代表蜜柑总数和chika吃的蜜柑数量。(1≤k≤n≤200000)

第二行有n个正整数ai，分别代表每个蜜柑的酸度。（1≤ai≤1e9）

第二行有n个正整数bi，分别代表每个蜜柑的甜度。（1≤bi≤1e9）

输出描述:

两个正整数，用空格隔开。分别表示总酸度和总甜度。

示例

输入

3 2

1 3 4

2 2 5

输出

5 7

说明

选择1号和3号蜜柑，总酸度为5，总甜度为7，为最优解。

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 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 < n; i++){

Orange orange = new Orange();

orange.acid = Integer.parseInt(ai[i]);

orange.sweet = Integer.parseInt(bi[i]);

queue.add(orange);

}

long totalAcid = 0;

long totalSweet = 0;

for(int i = 0; i < k; i++){

Orange o = queue.poll();

totalAcid += o.acid;

totalSweet += o.sweet;

}

System.out.println(totalAciRQqoRfBqd + " " + totalSweet);

}

}

目的：

了解什么是贪心，当设计到优先级时可以考虑使用PriorityQueue+Comparator。

算法题2：

you和帆船

难度 ⭐⭐

you的父亲是一名船长。因此you从小就很喜欢大海。这天，她乘着一艘帆船出发了。

大海上有很多宝藏，每个宝藏的坐标是已知的。you的初始坐标是（0,0）。她想探索两个宝藏，然后回到初始点。

you希望航线尽可能短。她想知道，最短航线的长度是多少？

题目信息：两个for循环枚举一下，再保存最短路径即可。

输入描述:

第一行一个正整数n，代表宝藏的数量。（2≤n≤2000）

接下来的n行，每行2个正整数xi，yi，代表第i个宝藏的坐标（-3000≤xi,yi≤3000）

不保证不存在两个宝藏位置相同。意思是，you可以在同一个位置探索这两个宝藏。

输出描述:

最短路线的长度。小数点后保留6位。

示例

输入

2

1 0

0 1

输出

3.414214

说明

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

String[] strings = br.readLine().split(" ");

Point point = new Point();

point.x = Integer.parseInt(strings[0]);

point.y = Integer.parseInt(strings[1]);

points[i] = point;

}

double min = Double.MAX_VALUE;//定义最大值，寻找较小值

//双层遍历枚举

for (int i=0;i

for (int j=i+1;j

double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)

+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)

+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));

min = Math.min(min, temp);

}

}

System.out.println(String.format("%.6f", min));

}

}

目的：

了解什么是枚举，虽然是一个一个列举，但是结合实际还是有优化的方式。

比如此题两层循环只枚举了一半的情况：因为所求的是距离，跟两个端点无关。

思考：

假如不止有两个宝箱需要被获取，那么应该怎么办？？？下一题可以参考一下。

算法题3：

数位染色

难度 ⭐⭐⭐

小红拿到了一个正整数 X 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。

她不知道能不能达成目标。你能告诉她吗？

输入描述:

一个正整数X ，1<= X <=10^18

输出描述:

如果小红能按要求完成染色，输出"Yes"。否则输出"No"。

示例1

输入

1234567

输出

Yes

说明

将3、4、7染成红色即可，这样3+4+7=1+2+5+6

示例2

输入

23

输出

No

说明

显然无论如何都不能完成染色。

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<1<<19;i++){

long p=i,s1=0,s2=0,temp=x;

//将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。

for(int j=0;j<19;j++){

if(p%2==1)s1+=temp%10;

else s2+=temp%10;

p/=2;

temp/=10;

}

if(s1==s2){

System.out.println("Yes");

System.exit(0);

}

}

System.out.println("No");

}

}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

for(int i=0;i<1<<19;i++)

//修改成

for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;

for(int i=0;i

当然这题也可以使用背包或dfs来解答。

算法题4：

ranko的手表

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

ranko 在 t1 时刻看了下时间，过了一段时间在 t2 时刻看了下时间。她想知道， t1  和t2这两个时刻之间相距的时间的最大值和最小值是多少？

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。

输入描述:

两行输入两个时间，为 xx:xx 的形式。其中 x 为数字或者字符 '?' ，问号代表这个数字没有显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

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 a1 = new ArrayList<>();

ArrayList a2 = new ArrayList<>();

for(int i = 0; i < 60*24; i++){

int hour = i/60, minute = i%60;

if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&

(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&

(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&

(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);

if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&

(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&

(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&

(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);

}

int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for(int i = 0; i

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

String[] strings = br.readLine().split(" ");

Point point = new Point();

point.x = Integer.parseInt(strings[0]);

point.y = Integer.parseInt(strings[1]);

points[i] = point;

}

double min = Double.MAX_VALUE;//定义最大值，寻找较小值

//双层遍历枚举

for (int i=0;i

for (int j=i+1;j

double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)

+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)

+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));

min = Math.min(min, temp);

}

}

System.out.println(String.format("%.6f", min));

}

}

目的：

了解什么是枚举，虽然是一个一个列举，但是结合实际还是有优化的方式。

比如此题两层循环只枚举了一半的情况：因为所求的是距离，跟两个端点无关。

思考：

假如不止有两个宝箱需要被获取，那么应该怎么办？？？下一题可以参考一下。

算法题3：

数位染色

难度 ⭐⭐⭐

小红拿到了一个正整数 X 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。

她不知道能不能达成目标。你能告诉她吗？

输入描述:

一个正整数X ，1<= X <=10^18

输出描述:

如果小红能按要求完成染色，输出"Yes"。否则输出"No"。

示例1

输入

1234567

输出

Yes

说明

将3、4、7染成红色即可，这样3+4+7=1+2+5+6

示例2

输入

23

输出

No

说明

显然无论如何都不能完成染色。

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<1<<19;i++){

long p=i,s1=0,s2=0,temp=x;

//将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。

for(int j=0;j<19;j++){

if(p%2==1)s1+=temp%10;

else s2+=temp%10;

p/=2;

temp/=10;

}

if(s1==s2){

System.out.println("Yes");

System.exit(0);

}

}

System.out.println("No");

}

}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

for(int i=0;i<1<<19;i++)

//修改成

for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;

for(int i=0;i

当然这题也可以使用背包或dfs来解答。

算法题4：

ranko的手表

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

ranko 在 t1 时刻看了下时间，过了一段时间在 t2 时刻看了下时间。她想知道， t1  和t2这两个时刻之间相距的时间的最大值和最小值是多少？

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。

输入描述:

两行输入两个时间，为 xx:xx 的形式。其中 x 为数字或者字符 '?' ，问号代表这个数字没有显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

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 a1 = new ArrayList<>();

ArrayList a2 = new ArrayList<>();

for(int i = 0; i < 60*24; i++){

int hour = i/60, minute = i%60;

if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&

(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&

(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&

(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);

if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&

(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&

(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&

(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);

}

int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for(int i = 0; i

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

for (int j=i+1;j

double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)

+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)

+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));

min = Math.min(min, temp);

}

}

System.out.println(String.format("%.6f", min));

}

}

目的：

了解什么是枚举，虽然是一个一个列举，但是结合实际还是有优化的方式。

比如此题两层循环只枚举了一半的情况：因为所求的是距离，跟两个端点无关。

思考：

假如不止有两个宝箱需要被获取，那么应该怎么办？？？下一题可以参考一下。

算法题3：

数位染色

难度 ⭐⭐⭐

小红拿到了一个正整数 X 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。

她不知道能不能达成目标。你能告诉她吗？

输入描述:

一个正整数X ，1<= X <=10^18

输出描述:

如果小红能按要求完成染色，输出"Yes"。否则输出"No"。

示例1

输入

1234567

输出

Yes

说明

将3、4、7染成红色即可，这样3+4+7=1+2+5+6

示例2

输入

23

输出

No

说明

显然无论如何都不能完成染色。

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<1<<19;i++){

long p=i,s1=0,s2=0,temp=x;

//将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。

for(int j=0;j<19;j++){

if(p%2==1)s1+=temp%10;

else s2+=temp%10;

p/=2;

temp/=10;

}

if(s1==s2){

System.out.println("Yes");

System.exit(0);

}

}

System.out.println("No");

}

}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

for(int i=0;i<1<<19;i++)

//修改成

for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;

for(int i=0;i

当然这题也可以使用背包或dfs来解答。

算法题4：

ranko的手表

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

ranko 在 t1 时刻看了下时间，过了一段时间在 t2 时刻看了下时间。她想知道， t1  和t2这两个时刻之间相距的时间的最大值和最小值是多少？

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。

输入描述:

两行输入两个时间，为 xx:xx 的形式。其中 x 为数字或者字符 '?' ，问号代表这个数字没有显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

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 a1 = new ArrayList<>();

ArrayList a2 = new ArrayList<>();

for(int i = 0; i < 60*24; i++){

int hour = i/60, minute = i%60;

if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&

(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&

(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&

(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);

if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&

(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&

(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&

(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);

}

int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for(int i = 0; i

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y)

+ Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y)

+ Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));

min = Math.min(min, temp);

}

}

System.out.println(String.format("%.6f", min));

}

}

目的：

了解什么是枚举，虽然是一个一个列举，但是结合实际还是有优化的方式。

比如此题两层循环只枚举了一半的情况：因为所求的是距离，跟两个端点无关。

思考：

假如不止有两个宝箱需要被获取，那么应该怎么办？？？下一题可以参考一下。

算法题3：

数位染色

难度 ⭐⭐⭐

小红拿到了一个正整数 X 。她可以将其中一些数位染成红色。然后她想让所有染红的数位数字之和等于没染色的数位数字之和。

她不知道能不能达成目标。你能告诉她吗？

输入描述:

一个正整数X ，1<= X <=10^18

输出描述:

如果小红能按要求完成染色，输出"Yes"。否则输出"No"。

示例1

输入

1234567

输出

Yes

说明

将3、4、7染成红色即可，这样3+4+7=1+2+5+6

示例2

输入

23

输出

No

说明

显然无论如何都不能完成染色。

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<1<<19;i++){

long p=i,s1=0,s2=0,temp=x;

//将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。

for(int j=0;j<19;j++){

if(p%2==1)s1+=temp%10;

else s2+=temp%10;

p/=2;

temp/=10;

}

if(s1==s2){

System.out.println("Yes");

System.exit(0);

}

}

System.out.println("No");

}

}

这题使用的是状压枚举

只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）

for(int i=0;i<1<<19;i++)

//修改成

for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;

for(int i=0;i

当然这题也可以使用背包或dfs来解答。

算法题4：

ranko的手表

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

ranko 在 t1 时刻看了下时间，过了一段时间在 t2 时刻看了下时间。她想知道， t1  和t2这两个时刻之间相距的时间的最大值和最小值是多少？

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。

输入描述:

两行输入两个时间，为 xx:xx 的形式。其中 x 为数字或者字符 '?' ，问号代表这个数字没有显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

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 a1 = new ArrayList<>();

ArrayList a2 = new ArrayList<>();

for(int i = 0; i < 60*24; i++){

int hour = i/60, minute = i%60;

if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&

(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&

(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&

(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);

if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&

(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&

(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&

(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);

}

int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for(int i = 0; i

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

当然这题也可以使用背包或dfs来解答。

算法题4：

ranko的手表

难度 ⭐⭐⭐⭐

ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。

ranko 在 t1 时刻看了下时间，过了一段时间在 t2 时刻看了下时间。她想知道， t1  和t2这两个时刻之间相距的时间的最大值和最小值是多少？

保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。

输入描述:

两行输入两个时间，为 xx:xx 的形式。其中 x 为数字或者字符 '?' ，问号代表这个数字没有显示。保证输入是合法的。

输出描述:

一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。

示例

输入

18:0?

2?:1?

输出

121 319

说明

相距最小的时间为 18:09 到 20:10 ，相距121分钟。

相距最大的时间为 18:00 到 23:19 ，相距319分钟。

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 a1 = new ArrayList<>();

ArrayList a2 = new ArrayList<>();

for(int i = 0; i < 60*24; i++){

int hour = i/60, minute = i%60;

if((hour/10 == s1.charAt(0)-'0' || s1.charAt(0) == '?') &&

(hour%10 == s1.charAt(1)-'0' || s1.charAt(1) == '?') &&

(minute/10 == s1.charAt(3)-'0' || s1.charAt(3) == '?') &&

(minute%10 == s1.charAt(4)-'0' || s1.charAt(4) == '?')) a1.add(i);

if((hour/10 == s2.charAt(0)-'0' || s2.charAt(0) == '?') &&

(hour%10 == s2.charAt(1)-'0' || s2.charAt(1) == '?') &&

(minute/10 == s2.charAt(3)-'0' || s2.charAt(3) == '?') &&

(minute%10 == s2.charAt(4)-'0' || s2.charAt(4) == '?'))a2.add(i);

}

int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for(int i = 0; i

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

for(int j = 0; j

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

if(a1.get(i)

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

min = Math.min(min,a2.get(j)-a1.get(i));

max = Math.max(max,a2.get(j)-a1.get(i));

}

}

}

System.out.print(min + " " + max);

}

}

假如此题不使用枚举，则会限定很多条件。还不如直接都列举出来

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。