蓝桥杯|历届真题:作物杂交

jupiter
2022-03-20 / 0 评论 / 839 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月20日,已超过706天没有更新,若内容或图片失效,请留言反馈。

1.题目

【问题描述】
作物杂交是作物栽培中重要的一步。已知有$N$种作物(编号$1$至$N$),第$i$种作物从播种到成熟的时间为$T_i$。作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。如作物$A$种植时间为5天,作物$B$种植时间为7天,则$AB$杂交花费的时间为7天。作物杂交会产生固定的作物,新产生的作物仍然属于N种作物中的一种。
初始时,拥有其中$M$种作物的种子(数量无限,可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子,最少需要多少天能够得到。
如存在4种作物$ABCD$,各自的成熟时间为5天、7天、3天、8天。初始拥有AB两种作物的种子,目标种子为$D$,已知杂交情况为$A \times B→C,A \times C→D$。则最短的杂交过程为:

第1天到第7天(作物B的时间),$A \times B→C$。
第8天到第12天(作物A的时间),$A \ times C→D$。
花费12天得到作物D的种子。

【输入格式】
输入的第1行包含4个整数$N,M,K,T,N$表示作物种类总数(编号1至$N$),$M$表示初始拥有的作物种子类型数量,$K$表示可以杂交的方案数,$T$表示目标种子的编号。
第2行包含$N$个整数,其中第i个整数表示第i种作物的种植时间T;($1 \leq T_i \leq 100$)
第3行包含$M$个整数,分别表示已拥有的种子类型$K_j( 1 \leq K_j \leq M)$,$K_j$两两不同。
第4至$K+3$行,每行包含3个整数$A,B,C$,表示第$A$类作物和第$B$类作物杂交可以获得第$C$类作物的种子。

【输出格式】
输出一个整数,表示得到目标种子的最短杂交时间。
【样例输入】

6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6

【样例输出】

16

【样例说明】
第1天至第5天,将编号1与编号2的作物杂交,得到编号3的作物种
第6天至第10天,将编号1与编号3的作物杂交,得到编号4的作物种
第6天至第9天,将编号2与编号3的作物杂交,得到编号5的作物种
第11天至第16天,将编号4与编号5的作物杂交,得到编号6的作物种
总共花费16天
【评测用例规模与约定】
对于所有评测用例,$1 \leq N \leq 2000,2 \leq M \leq N,1 \leq K \leq 100000,1 \leq T \leq N$,保证目标种子一定可以通过杂交得到。

2. 题解

2.1 思路分析

思路1:暴力求解
设置一个数字minGetTime用于保存每类种子的最小获取时间
循环遍历杂交方案:
    minGetTime[C] = min(minGetTime[C],maxAB获取时间+maxAB成熟数据)
    直至数组minGetTime收敛(不再有任何位置发生变化)

2.2 代码实现

import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    
    // 判断minGetTime数组是否收敛|是否存在某位发生修改 无则返回true
    public static boolean isNoChange(boolean[] changeFlag){
        boolean res = true;
        for (int i = 0; i < changeFlag.length; i++) {
            res = res&changeFlag[i];
        }
        return res;
    }


    public static void main(String[] args) {
        int N = scanner.nextInt(); // 作物种类数
        int M = scanner.nextInt(); // 初始时候拥有的种子数量
        int K = scanner.nextInt(); // 可以杂交的方案数量
        int T = scanner.nextInt(); // 目的种子编号

        int[] timeSpendArr = new int[N];// 作物成熟时间
        for (int i = 0; i < N; i++) {
            timeSpendArr[i] = scanner.nextInt();
        }

        int[] startSeedArr = new int[M]; //初始拥有的种子
        for (int i = 0; i < M; i++) {
            startSeedArr[i] = scanner.nextInt();
        }

        int[][] methodArr = new int[K][3]; //杂交方案数
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 3; j++) {
                methodArr[i][j] = scanner.nextInt();
            }
        }

        int[] minGetTime = new int[N];//最小获取时间

        // 初始化最小获取时间
        for (int i = 0; i < N; i++) {
            minGetTime[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < M; i++) {
            minGetTime[startSeedArr[i]-1] = 0;
        }

        boolean[] changeFlag = new boolean[K];//用于判断本轮处理杂交方案是否导致了最小时间发生修改|判断收敛
        Arrays.fill(changeFlag,false);
        while (!isNoChange(changeFlag)){//知道未发生修改位置
            Arrays.fill(changeFlag,true);
            for (int i = 0; i < K; i++) {
                int seedA = methodArr[i][0]-1;
                int seedB = methodArr[i][1]-1;
                if(minGetTime[seedA]==Integer.MAX_VALUE||minGetTime[seedB]==Integer.MAX_VALUE)continue;
                int newSeed = methodArr[i][2]-1;//新品种
                int minGetTimeOfNewSeed = Math.min(minGetTime[newSeed],Math.max(minGetTime[seedA],minGetTime[seedB])+Math.max(timeSpendArr[seedA],timeSpendArr[seedB]));
                if(minGetTimeOfNewSeed!=minGetTime[newSeed]){
                    changeFlag[i] = false;
                    minGetTime[newSeed] = minGetTimeOfNewSeed;
                }
            }
        }

        System.out.println(minGetTime[T-1]);
    }
}

2.3 提交结果

评测点序号评测结果得分CPU使用内存使用下载评测数据
1正确10.00125ms25.54MB输入 输出
2正确10.00109ms25.46MBVIP特权
3正确10.00468ms75.14MBVIP特权
4正确10.00406ms68.42MBVIP特权
5正确10.00390ms77.67MBVIP特权
6正确10.00296ms54.73MBVIP特权
7正确10.00500ms99.37MBVIP特权
8正确10.00453ms98.50MBVIP特权
9正确10.00578ms97.82MBVIP特权
10正确10.00500ms98.80MBVIP特权

参考资料

  1. http://lx.lanqiao.cn/problem.page?gpid=T2859
0

评论 (0)

打卡
取消