大疆 2023/08/13【笔试真题】_大疆笔试

前言

2023-8-23 16:38:33

以下内容源自《【笔试真题】》
仅供学习交流使用

版权

禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话

推荐

无

大疆 2023/08/13

1 无人机环形路线-贪心算法

环形路线，n个充电站，编号0,…,n-1，i号充电站提供charge[i]的电量

无人机从i号充电站，飞往i+1充电站，消耗cost[i]

问无人机是否能够从某一充电站出发，绕一圈返回；
能返回输出起始站，否则返回-1。

输入提供的电量
输入消耗的电量

输入
5
1 2 3 4 5
5
3 4 5 1 2

输出
3
1
2
3
4
5
6
7
8

解法

package test0813;

import java.util.*;


/*
输入
5
1 2 3 4 5
5
3 4 5 1 2

输出
3
 */
public class Main1 {
    static class Solution {

        /* Write Code Here */
        public int circle_fly(int[] charge, int[] cost) {
            int sumCharge =0;
            int sumCost =0;
            for(int c:charge) sumCharge +=c;
            for(int c:cost) sumCost +=c;
            if(sumCharge < sumCost) return -1;
            int countStations =charge.length;
            int currentCharge=0;
            int beginStation =0;
            for(int i = 0; i< countStations; i++){
                currentCharge+=charge[i]-cost[i];
                if(currentCharge<0){
                    currentCharge=0;
                    beginStation =i+1;
                }
            }
            return beginStation;

        }
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int res;

        int charge_size = 0;
        charge_size = in.nextInt();
        int[] charge = new int[charge_size];
        for(int charge_i = 0; charge_i < charge_size; charge_i++) {
            charge[charge_i] = in.nextInt();
        }

        if(in.hasNextLine()) {
            in.nextLine();
        }

        int cost_size = 0;
        cost_size = in.nextInt();
        int[] cost = new int[cost_size];
        for(int cost_i = 0; cost_i < cost_size; cost_i++) {
            cost[cost_i] = in.nextInt();
        }

        if(in.hasNextLine()) {
            in.nextLine();
        }

        res = new Solution().circle_fly(charge, cost);
        System.out.println(String.valueOf(res));

    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

2 动态规划

LCP 35. 电动车游城市

解答

package test0813;

import java.util.*;

/*



LCP 35.电动车游城市
https://leetcode.cn/problems/DFPeFJ/

小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间。
小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1。
他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，表示城市 A、B 间存在双向通路。
初始状态，电动车电量为 0。每个城市都设有充电桩，
charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end。

输入样式：
第一行表示n个path，宽度是3
接下来n行的path
输入cnt
输入start
输入end
输入charge[]的长度
输入charge[]

输出样式
最少单位时间

样例输入
5 3
1 3 3
3 2 1
2 1 3
0 1 4
3 0 5
6
1
0
4
2 10 4 1

样例输入
6 3
0 4 2
4 3 5
3 0 5
0 1 5
3 2 4
1 2 8
8
0
2
5
4 1 1 3 2

样例输出
38
 */


public class Main2 {

    /**
     * 首先建图， 存储每个城市相邻的城市和距离
     *
     * 使用一个二维数组保存结果arr[i][j] = k， i = 所在城市， j = 剩余电量， k = 最短时间
     *
     * 用队列来记录每个路径的信息 {time,cur,power}， time = 已用时间， cur = 所在城市， power = 剩余电量 (使用优先队列来保证每次优先执行已用时间最少的路径)
     *
     * 每次只会有两种操作
     *
     * 充一次电 - 新时间 = 已用时间 + 当前城市每单位充电需要时间， 新电量 = 剩余电量 + 1
     * 去往下一个城市 - 新时间 = 已用时间 + 去往该需要消耗的时间， 新电量 = 剩余电量 − 去往该城市需要消耗的电量
     *
     * 作者：Feilulue 
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/994121