第十一周

川长思鸟来 2023-01-21 11:25 1阅读 0赞

### 记录2021OJ ###

*  A.最少素数
 *   *   *  代码
 *  B.安置路灯
 *   *   *  代码
 *  C.最小硬币
 *   *   *  代码
 *  D.图书排序
 *   *   *  代码
 *  E.月饼
 *   *   *  代码
 *  F.汽车加油问题
 *   *   *  代码

# A.最少素数 #

**题目描述**

*  小X刚刚学习了素数的定义，现在给定一个正整数N，小X希望知道N最少表示成多少个素数的和。
 *  素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

**提示**

*  哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。

**输入**

*  输入一个正整数n（n<=1e9）。多组输入。

**输出**

*  组成n的素数个数。

**样例输入 Copy**

3
    6

**样例输出 Copy**

1
    2

**提示**

1.  3本身就是1个素数。
2.  6可以表示为3 + 3，注意同样的素数可以使用多次。

> 【没啥好说的，总不能说我在毛概课上写题吧，就是判断奇偶那里开始出了问题，就是判断不了2，然后又找了很多代码，最后找到了下面这篇】  
> 【链接：[戳我戳我！][Link 1]】

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    	public static boolean select_prime(int n){ 
    		if(n<2)
    			return true;
    		
    		for(int i=2;i*i<=n;i++)
    			if(n%i==0)
    				return false;
    		return true;
    	}
    
    	public static int min_prime(int n){ 
    		
    		if(select_prime(n))//是素数返回1
    			return 1;
    		
    		if(n%2==0){ //偶数
    			if(n==2)//2也是素数，返回1
    				return 1;
    			else
    				return 2;
    		}
    		else{ //非偶数非素数
    			if(select_prime(n-2))//如果N - 2是素数那N=（N-2）+2;2也是素数所以返回
    				return 2;
    			else
    				return 3;//这个数是奇数，所以N-1=偶数 偶数=两个素数之和 所以N = (N-1)+1 所以返回3
    		}
    			
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			System.out.println(min_prime(n));
    		}
    
    	}
    
    }

# B.安置路灯 #

**题目描述**

*  小Q正在给一条长度为n的道路设计路灯安置方案。
 *  为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.'表示, 不需要照亮的障碍物格子用’X’表示。
 *  小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
 *  小Q希望能安置尽量少的路灯照亮所有’.'区域, 希望你能帮他计算一下最少需要多少盏路灯。

**输入**

*  输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
 *  接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
 *  第二行一个字符串s表示道路的构造,只包含’.‘和’X’。

**输出**

*  对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。

**样例输入 Copy**

2
    3
    .X.
    11
    ...XX....XX

**样例输出 Copy**

1
    3

> 【刚开始没看懂，第一反应就是CSDN找题，看别人的代码，看了半天，找到了一篇链接:[戳一戳呀~][Link 2]】

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();//两组测试案例
    			for(int i = 0;i<n;i++){ //循环测试案例
    				int L = sc.nextInt();//道路的长度
    				String road = sc.next();//表示道路的构造,只包含'.'和'X'
    				int count = 0;//计数需要照亮的
    				for(int j=0;j<L;j++){ 
    					if(road.charAt(j)=='.'){ 
    						count++;
    						j+=2;
    					}
    				}
    				System.out.println(count);
    			}
    
    	}
    
    }

# C.最小硬币 #

**题目描述**

*  假设有4种硬币，它们的面值分别为1分、5分、10分和25分。
 *  现在要找给顾客n分钱
 *  请问怎样找零钱才能使给顾客的硬币个数最少？
 *  输出所需最少硬币的枚数。

**输入**

*  输入需要找给顾客的零钱n（单位：分）

**输出**

*  输出所需最少硬币的枚数。

**样例输入 Copy**

8
    10
    63

**样例输出 Copy**

4
    1
    6

> 【老师上课的时候讲过，硬币面值（3个及以上）构成等比数列一定可以使用贪心算法求出最优解，但是不构成等比数列使用贪心算法不一定求出最优解，也不是一定不能啦，1,5,10,25，这套面值可以使用贪心算法求解！  
> 链接:[戳这里！戳这里！][Link 3]】

### 代码 ###

import java.util.Scanner;
    import java.util.Arrays;
    
    public class Main { 
    	
        public static int Coins(int[] v,int n,int [][]c){ 
        	
            for(int i=0;i<=v.length;i++)
                c[i][0]=0;
            for(int i=0;i<=n;i++)
                c[0][i]=Integer.MAX_VALUE;
            
            for(int i=1;i<=n;i++){ //钱
                for(int j=1;j<= v.length;j++){ //面值
                    if(i<v[j-1]){ 
                        c[j][i]=c[j-1][i];
                        continue;
                    }
                    if(c[j-1][i]<(c[j][i-v[j-1]]+1))
                        c[j][i] = c[j-1][i];
                    else
                        c[j][i] = c[j][i-v[j-1]]+1;
                }
            }
            return c[v.length][n];
        }
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int[] v = { 1,5,10,25};
            
            Arrays.sort(v);//排序
            
    		while(sc.hasNext()) { 
    			int n=sc.nextInt();
    			int[][] c = new int[v.length+1][n+1];
                System.out.println(Coins(v,n,c));
            }
        }
    }

# D.图书排序 #

**题目描述**

*  某图书销售管理系统需要对图书(Book)进行排序，每一本图书包含书名(bookName)、销量(bookSales)、价格(bookPrice)等属性，要求先按照销量由大到小排序，对于销量相同的图书再按照价格由小到大排序。

**输入**

*  每组输入包括两个部分，第一部分为书的数量n， 接下来n行则为n本书的信息。 按顺序输入书名(不超过20个字)、销量、价格。

**输出**

*  输出排序后的信息，每个属性用空格隔开

**样例输入 Copy**

7
    C++程序设计 120 25.00
    软件工程 96 48.00
    高等数学 80 32.50
    算法分析与设计 96 54.00
    离散数学 96 28.00
    计算机网络 96 36.00
    操作系统 115 45.00

**样例输出 Copy**

C++程序设计 120 25.00
    操作系统 115 45.00
    离散数学 96 28.00
    计算机网络 96 36.00
    软件工程 96 48.00
    算法分析与设计 96 54.00
    高等数学 80 32.50

【直接上链接：[戳吧戳吧~][Link 3]】

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    
    	public static void swap(String []name,int []sale,float []price,int j){ 
    		String temp1 = name[j];
    		name[j] = name[j+1];
    		name[j+1] = temp1;
    		
    		int temp2 = sale[j];
    		sale[j] = sale[j+1];
    		sale[j+1] = temp2;
    		
    		float temp3 = price[j];
    		price[j]=price[j+1];
    		price[j+1]=temp3;
    
    	}
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			
    			int n = sc.nextInt();
    			String []name = new String[n+1];
    			int []sale = new int[n+1];
    			float []price = new float[n+1];
    			
    			for(int i=1;i<=n;i++){ 
    				name[i] = sc.next();
    				sale[i] = sc.nextInt();
    				price[i] = sc.nextFloat();
    			}
    			for(int i=1;i<=n;i++)
    				for(int j=1;j<=n-i;j++){ 
    					if(sale[j]<sale[j+1])//按销量从大到小排序
    						swap(name,sale,price,j);
    					else if(sale[j]==sale[j+1])//销量相等，则按价格从小到大排序
    						if(price[j]>price[j+1])
    							swap(name,sale,price,j);
    				}
    			for(int i=1;i<n+1;i++){ 
    				System.out.print(name[i]+" "+sale[i]+" ");
    				System.out.println(String.format("%1.2f", price[i]));
    			}
    		}
    	}
    }

# E.月饼 #

**题目描述**

*  月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
 *  注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼，获得72 + 45/2 = 94.5（亿元）。

**输入**

*  每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最大需求量。随后一行给出N个正实数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正实数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

**输出**

*  对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后2位。（四舍五入）

**样例输入 Copy**

3 20
    18 15 10
    75 72 45

**样例输出 Copy**

94.50

【和部分背包差不多，链接：[戳！给我使劲戳！][Link 3]】

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    	static double max = 0;
    	public static void swap(double []a,int i,int j){ 
    		double temp = a[i];
    		a[i] = a[j];
    		a[j] = temp;
    	}
    	public static void knapsack(double []v,double []w,int n,int c){ 
    		double []a = new double[n];
    		double []b = new double[n];
    		double weight = c;
    		
    		for(int i=0;i<n;i++)
    			a[i] = v[i]/w[i];//单位质量价值
    		for(int i=0;i<n;i++)
    			for(int j=0;j<n-i-1;j++){ 
    				if(a[j]<a[j+1]){ 
    					swap(w,j,j+1);
    					swap(v,j,j+1);
    					swap(a,j,j+1);
    				}
    			}
    		int k;
    		for(k=0;k<n;k++){ 
    			if(w[k]<=weight){ 
    				b[k] = 1;
    				weight-=w[k];
    			}
    			else
    				break;
    		}
    		if(k<n)
    			b[k] = (double)(weight/w[k]);
    		for(int i=0;i<b.length;i++)
    			max+=b[i]*v[i];
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			int c = sc.nextInt();
    			double v[] = new double[n];
    			double w[] = new double[n];
    			double x[] = new double[n];
    
    			for(int i=0;i<n;i++)
    				w[i] = sc.nextDouble();
    			for(int i=0;i<n;i++)
    				v[i] = sc.nextDouble();
    			knapsack(v,w,n,c);
    			System.out.printf("%.2f\n",max);
    		}
    	}
    }

# F.汽车加油问题 #

**题目描述**

*  一辆汽车加满油后可以行驶n千米。旅途中有k个加油站。若要使沿途的加油次数最少，请设计一个有效的算法。

**输入**

*  第一行有2个正整数n和k，表示汽车加满油后可行驶nkm，且旅途中有k个加油站。接下来1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油，且在第0个加油站满油不算加油，第k+1个加油站表示目的地。(请处理到文件尾)

**输出**

*  最少加油次数。如果无法到达目的地，则输出“No Solution”。

**样例输入 Copy**

7 7
    1 2 3 4 5 1 6 6

**样例输出 Copy**

> 【啊啊，这一题，着实困住了我，因为输出的时候出现了问题，没加一个用来判断的变量之前，输出的时候不仅会输出“No Solution”,还会输出计数的结果，所以就加了，然后就过了】

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    
    	static int sum,distance,n,k,b;
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();//可行驶n公里
    			int k = sc.nextInt();//m个加油站
    			int []a = new int[k+2];
    			distance = 0;//记录汽车行驶的距离
    			sum = 0;//加油次数
    			for(int i=1;i<=k+1;i++){ 
    				a[i] = sc.nextInt();//输入每个加油站距离下一个加油站的距离
    				if(a[i]>n)//两个加油站之间的距离大于汽车油箱最大行驶距离
    					b = 0;
    				else{ 
    					b = 1;
    					distance+=a[i];
    			        if(distance>n){ 
    				        sum++;//加油次数
    				        distance = a[i];
    			        }
    				}
    			}
    			if(b==0)
    				System.out.println("No Solution");
    			else
    				System.out.println(sum);
    		}
    	}
    }

> 【小编今日没事呀，都在写题，就分享句子吧~】
> 
> > 李嘉诚:  
> > 当你可以放下面子去挣钱的时候，  
> > 说明你已经懂事了;  
> > 当你可以用钱挣回面子的时候，  
> > 说明你已经成功了;  
> > 当你可以用你的面子去挣钱的时候，  
> > 说明你已经是个人物了;  
> > 如果你现在还在这儿天天唧唧歪歪嘚啵得  
> > 要面子抱着面子死守不放的时候，  
> > 说明你这辈子也就这样了。

[Link 1]: https://blog.csdn.net/qq_43191249/article/details/108640264
[Link 2]: https://blog.csdn.net/sinat_38648388/article/details/97914145
[Link 3]: https://blog.csdn.net/ZHANGQIANYI2020/article/details/112510432