母羊生羊问题（java）

母羊生羊问题

问题简述：开始有一只母羊，可以在n1,n2,n3…..年生产母羊，生产的母羊具有相同生育特性，并且所有的母羊生命为m年，求在x年后，所有的母羊总数

输入示例

2 4

5

10

输出

47

说明：

输入：母羊在第2年，第4年生育

母羊在第5年死去

求10年后母羊总数

输出：10年后母羊数

代码如下:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Sheep {
    public int age = ; // 默认一只新羊的年龄为0
}
public class T1 {


    public static int getSheeps(int n ,int[] arr,int dead) {
        // sheeps表示整个羊的生态圈
        ArrayList<Sheep> sheeps = new ArrayList<Sheep>();
        sheeps.add(new Sheep());

        List<Sheep> addSheeps = new ArrayList<Sheep>();//待添加到生态圈的新羊
        List<Sheep> delSheeps = new ArrayList<Sheep>();//待从生态圈删除的羊

        for (int i = ; i <= n; i++) {
            for (Sheep s : sheeps) {

                for (int j = ; j < arr.length; j++) {
                    if (s.age==arr[j]) {
                        Sheep temp = new Sheep();
                        temp.age++;
                        addSheeps.add(temp);
                    }
                }
                if (s.age==dead) {
                    delSheeps.add(s);
                }
                s.age++;
            }

            sheeps.addAll(addSheeps);
            sheeps.removeAll(delSheeps);
            addSheeps.clear();//清空addSheeps
            delSheeps.clear();//清空待删除列表中的元素

        }

         return sheeps.size(); // 最后总羊数即羊生态圈中的羊数目
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String brr[] = line.split(" ");

        int[] arr = new int[brr.length];
        for (int i = ; i < brr.length; i++) {
            arr[i] = Integer.parseInt(brr[i]);
        }

        int dead = sc.nextInt();
        int year = sc.nextInt();
        System.out.println(getSheeps(year,arr,dead));
    }
}
           

思路：维护一个现存活羊链表，一个出生母羊列表，一个死去的母羊列表，在活羊列表去除死羊，添加活羊即可