[数据结构与算法]蓝桥杯31天冲刺 Day5

猴子分香蕉

链接: 猴子分香蕉.

根据题意直接写就好了。
但是尤其要注意的是：第5只猴子醒来的时候得有香蕉！！！

代码：

package 题库;

public class 猴子分香蕉 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		float num=5+1;

        boolean flag = true;
        while(flag) {
        	//第一只
        	float n = ((num-1)/5)*4;
        	//第二只
        	n = ((n-2)/5)*4;
        	//第三只
        	n = ((n-3)/5)*4;
        	//第四只
        	n = ((n-4)/5)*4;
        	//第5只
        	if(n%5==0&&n/5>=1.0) {
        		System.out.println(num);
        		flag = false;
        	}
        	num+=1;
        }
	}

}

等差数列

链接: 等差数列.

这题也比较简单，我们只需找到相邻两项间最小的差再除以max-min的值加一就好了。（也就是说要把数列先排序）

import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = scan.nextInt();
        }
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        for (int i = 1 ; i < n ;i++){
            if (nums[i] - nums[i - 1] < min){
                min = nums[i] - nums[i - 1];
            }
        }
        if (min == 0){
            System.out.println(n);
            return;
        }
        int res = (nums[n - 1] - nums[0]) / min + 1;
        System.out.println(res);
        scan.close();
    }
}

平方序列

链接: 平方序列.

根据等差数列公式：a+c = 2b，枚举就可以得出答案了

代码：

import java.math.*;

public class 平方序列 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        boolean flag = true;
        int Y = 2021;
        while(flag) {
        	float x =(float) Math.sqrt((Y*Y+2019*2019)/2);
        	if(x%1==0&&x<Y&&x>2019) {
        		System.out.println(x);
        		System.out.println(Y);
        		System.out.println(x+Y);
        		flag = false;
        	}
        	Y+=1;
        }
	}

}

倍数问题

链接: 倍数问题.

这题要用到背包，我用dfs跑出来的肯定超时（先放一下bfs代码，巩固完背包问题以后再补上正确代码）

import java.util.*;

public class 倍数问题 {

	public static List<Integer> res = new ArrayList<>();
	public static int res1=0;
	
	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 k  =sc.nextInt();
        	int[] nums = new int[n];
        	for(int i =0;i<n;i++) {
        		nums[i]=sc.nextInt();
        	}
        	Arrays.sort(nums);
        	
        	findNums(nums,n-1,k);

        	System.out.println(res1);
        }
	}
	
	public static void findNums(int[] nums,int index,int k) {
		if(index<0||res.size()>3||res.size()+index<2) {
			return ;
		}
		if(res.size()==3) {
			int sum = res.get(0)+res.get(1)+res.get(2);
			if(sum%k == 0&&sum>res1) {
				res1=sum;
				
				return;
			}
				
		}
		
		for(int i =index;i>=0;i--) {
			res.add(nums[i]);
			findNums(nums,i-1,k);
			res.remove(res.size()-1);
		}
	}

}