笔试时间：2023年8月13日 服务端

第一题

题目：无人机飞行规划

给定一个环形路线实施无人机作业，在路线上有n个充电站，编号0... n-1，i号充电桩可以给无人机提供charge[i] 单位的电量，无人机从i号充电桩出发完 成作业，并飞往i+1号充电的需要消耗 cost[i] 单位的的电量。

假没无人机可以无限量充电。无人机从其中一个充电站完成充电出发(充电前初始电量为空)，给定正整数数组charge和cost，如果无人机可以顺时针绕环形路线一周完成作业并返回出发充电站，则返回出发时充电站的编号i，否则返回-1。

注，为简化问题，如果存在解，输入数据可保证解唯一。测试用例输入格式为 (length of charge,charge,length of cost,cost).

样例输入输出1

示例1

输入:

length of charge = 5, charge = [1,2,3,4,5], length of cost = 5, cost = [3,4,5,1,2]

输出:

3

解析:从3号充电站出发，电量为4;飞到4号充电站，电量为4-1+5=8;飞到0号充电站，电量为8-2+1=7;飞到1号充电站，电量为7-3+2=6;飞到2号充 电站，电量为6-4+3=5;飞回到3号充电站，电量5正好满足cost[2]

样例输入输出2

示例2

输入:

length of charge = 3,charge = [2,3.4], length of cost = 3,cost = [3,4,3]

输出:

-1

解析: 从0号或者号充电站出发，得到的电量都不能满定经下一站的电量。从2号充电站出发，电量为4:飞到0号充电站，电量为4-3+2=3;飞到1号充电站，电量为3-3+3=3;但是无法返回2号充电站， cost[1]>3.

参考题解

参考leetcode 134

Python：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        diff = [gas[i] - cost[i]  for i in range(n)]
        if sum(diff) < 0: return -1
        sum_ = list(accumulate(diff,initial=0))
        return sum_.index(min(sum_)) 

第二题

题目：最短航拍时间

周末放假了，小疆计划骑着自己的电动车去航拍。小疆打开DiiFly上的去哪拍，找到了多个航拍点。为了规划路线，小疆提前了解了不同的航拍点之间的连通性和距离，同时还确认了每个航拍点充电桩的充电速率。小疆的电动车满电电量可行驶的距离为dis，单位km，该电动车每行驶1km消耗1单位电量，且耗费1min，一共N个航拍点，每个航拍点都有充电桩，使用二维数组paths标识两个航拍点的双向连通性和距离:[[航拍点编号，相邻航拍点编号，两个航拍点的距离]]，示例: [[0,1,3],[0,2,2]...],其中[0,1.3]就表示编号为0的航拍点和编号为1的航拍点相距3km，所有航拍点间的距离都小于dis，数组charge表示在每个航拍点充1单位电的花费的分钟数，示例: [2,10]，2表示编号为0的航拍点充电1单位耗时2分钟，10表示编号为1的航拍点充电1单位耗时10分钟。小疆当前在航拍点a，且电动车无电，请问小疆最少花费多少分钟数从所在的航拍点a抵达航拍点b。

输入描述

1、paths: 标识两个航拍点的双向连通性和距离 (先输入航拍点距离的二维数组长度，比如6 3，表示6组数据，每 组3个数值。再跟具体的数组内容) 2、dis: 电动车满电行驶里程 3、a: 航拍点a的编号 4、b: 航拍点b的编号 5、charge: 标识每个航拍点充1单位电的花费的分钟数 (先输入充电的数组长度，比如5。再跟数组内容，比如4 1 1 3

输出描述

最少花费的分钟数

样例输入

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

参考题解

Java：

import java.util.*;

public class Main {

    int[][] paths;
    int n;
    int dis, a, b;

    int[] times;

    List<List<int[]>> graph = new ArrayList<>();


    void solve(){
        Scanner sc = new Scanner(System.in);
        int y = sc.nextInt();
        int m = sc.nextInt();
        paths = new int[y][m];
        for (int i = 0; i < y; i++) {
            paths[i][0] = sc.